(All numbers here are from code that's been tested only in the trivial sense that I've run it and not noticed that the answers are obviously wrong. Don't trust them.) On 30/03/2013 02:04, Dan Asimov wrote:
For instance 46 = 4*11 + 2, 126 = 5^3 + 1, 144 = 11*13 + 1.
46 = 2*23, surely.
Having checked up to only 150 (by hand), things I don't know yet include
* What is the 2nd case ending with + 2 (other than 2 itself) ? (46 is the first.)
No (see above), 176 appears to be the first, followed by 225, then 325, 351, 385, 400, 441, 456, 476, 495, 540, 561, 576, 595, 715, 736, 760, 833, 875, 897, 936. (That's it up to 1000.)
* What is the first case ending with + 3 (other than 3) ?
352, 442, 1276, 1520, 1666, 1702, 1887. (That's it up to 2000.)
* What is the first case having a term K*2^r with r >= 1 (other than powers of 2 themselves) ? (This is not counting terms of the form K*p^r where p > 2 and K is a power of 2, such as 108 = 4*3^3.)
Powers of 2 (of course); 513 = 512 + 1; many many that end with "+ 2"; and (up to 10000) the following ending with other powers of 2: 4961, 5831, 6786, 7140, 7505. Unless I've misunderstood your definitions, in this case you always have K=1 because 1 <= K < p.
* What is the first case with more than two terms altogether?
None below 11000000. First appearances of every "tail", as far as my little program has got: 1 : 1 [empty tail] 12 : 1.11^1 + 1 176 : 6.29^1 + 1.2^1 352 : 1.349^1 + 1.3^1 2109 : 5.421^1 + 1.2^2 5832 : 1.5827^1 + 1.5^1 28037 : 1.28031^1 + 2.3^1 290789 : 2.145391^1 + 1.7^1 290790 : 2.145391^1 + 1.2^3 1255508 : 7.179357^1 + 1.3^2 4325179 : 3.1441723^1 + 2.5^1 11135847 : 4.2783959^1 + 1.11^1 ... from which, super-crudely, it looks like we might expect to see "+12" somewhere around 40 million, at which point we'd get three terms. My code is shockingly inefficient and hasn't got nearly that far yet. The right way to implement this is probably to generate all the k.p^r values in order and look at the gaps between them. I've taken the more naive approach of just computing the "variable prime-power base" representation separately for each n. So, anyway, it looks a little as if the "remainder" after pulling out the first term from n grows rather slowly; maybe something like log(n). I bet that whatever the fact is is hard to prove, but is some good bound implied by any standard theorem or conjecture about the distribution of primes? -- g