View Proposal #506
If this proposal belongs to you, you are authorized to update it. Use the menu on the right.
| ID | 506 |
|---|---|
| First Name | Joshua |
| Last Name | Zelinsky |
| Institution | ISU |
| Speaker Category | faculty |
| Title of Talk | Lower and upper bounds in integer complexity. |
| Abstract | Define ||n|| to be the complexity of n, the smallest number of 1's needed to write n using an arbitrary combination of addition and multiplication. John Selfridge showed that ||n|| is at least 3log3n for all n, and this lower bound is obtained exactly when n is a power of 3. Richard Guy noted the trivial upper bound of 3log_2 n for all n bigger than 1, by writing n in base 2. This talk will discuss work improving the upper bound, as well as work leading to a complete classification of numbers whose complexity is close to the lower bound. Along the way, we'll develop connections to both ordinal numbers and the p-adics. |
| Subject area(s) | Number theory |
| Suitable for undergraduates? | Y |
| Day Preference | SaturdayStrong |
| Computer Needed? | Y |
| Bringing a laptop? | N |
| Overhead Needed? | N |
| Software requests | |
| Special Needs | |
| Date Submitted | 09/17/2018 |
| Year | 2018 |