[seqfan] 'Climb to a prime' in other bases

[David Seal]

The recent posts about 13532385396179, http://oeis.org/A080670 and http://oeis.org/A195264 caused me to wonder whether similar numbers exist when you write them in bases other than 10. I've done some computer investigations of the question, so far only using 'brute force' programs (I've got a number of ideas how to improve on them), with the following results:

First, there are a couple of very simple examples in bases 6 and 8:

base-6 24 = decimal 16 = decimal 2^4 = base-6 2^4

base-8 33 = decimal 27 = decimal 3^3 = base-8 3^3

More generally, for any prime p and integer n > 0, the 2-digit number with digits p, np is equal to p^np in base b = p^(np-1)-n. That doesn't lead to a solution for the (p,n) = (2,1) combination, since that implies b=1 and so has the problem that the digits are >= the base, but otherwise it works, leading to a doubly-infinite family of bases in which examples exist, the next one of which is 29:

base-29 26 = decimal 64 = decimal 2^6 = base-29 2^6

Other than that, I have tried all bases from 2 to 20, and found examples in bases 2, 11 and 12:

binary 111110011111110011
= decimal 255987
= decimal 3^3 * 19 * 499
= binary 11^11 * 10011 * 111110011

base-11 3518
= decimal 4617
= decimal 3^5 * 19
= base-11 3^5 * 18

base-12 15287
= decimal 29767
= decimal 17^2 * 103
= base-12 15^2 * 87

In binary, I've also found a couple of 'amicable pairs', in which the operation of writing down the factorisation and then concatenating the primes and exponents on each number in the pair produces the other one. The first is:

binary 1111101111
= decimal 1007
= decimal 19 * 53
= binary 10011 * 110101

binary 10011110101
= decimal 1269
= decimal 3^3 * 47
= binary 11^11 * 101111

and the second is:

binary 10111011111
= decimal 1503
= decimal 3^2 * 167
= binary 11^10 * 10100111

binary 111010100111
= decimal 3751
= decimal 11^2 * 31
= binary 1011^10 * 11111

And the first of those two happens to work in base 4 as well:

base-4 33233
= decimal 1007
= decimal 19 * 53
= base-4 103 * 311

base-4 103311
= decimal 1269
= decimal 3^3 * 47
= base-4 3^3 * 233

So the 'climb to a prime' conjecture is false in bases 2, 4, 6, 8, 10, 11, 12, 29 and the various higher bases of the form p^(np-1)-n with p prime, n >= 2.

There are also various negative results - these are obviously dependant on there being no as-yet-undetected bugs in the programs I've written. They search for length-L "loops" in iterative application of the operation, where a number produces itself after L applications of the operation (so the 'amicable pairs' are length-2 loops and the other examples above are length-1 loops). More specifically, they search for non-prime maximal elements of loops, which are obviously in 1-to-1 correspondence with loops other than the length-1 loops that contain a prime number only. The results are:

Bases 2-6: No non-prime maximal elements of loops found other than those listed above (1269, 3751 and 255987 in base 2; 1269 in base 4; 16 in base 6) up to 6.5*10^8. (Programs are still running, so that limit will probably increase over time.)

Bases 7-20: No non-prime maximal elements of loops found other than those listed above (27 in base 8; 4617 in base 11; 29767 in base 12) up to 7^10, 8^10, 9^9, 10^9, 11^8, 12^8, 13^8, 14^7, 15^7, 16^7, 17^7, 18^7, 19^7, 20^6 respectively. (These results were obtained by an earlier, memory-bound version of the program, which I am no longer running.)

There's obviously the beginnings of an integer sequence here, defined as the smallest maximal element of a sequence generated by the 'climb to a prime' operation in base N that doesn't actually climb to a prime, or -1 if no such sequence has a maximal element. But 1269, ?, 1269, ?, 16, ?, 27, ?, ?(<=13532385396179), 4617, 29767, ... is probably a bit too little knowledge to register an OEIS sequence on!

David Seal