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

Neil Sloane njasloane at gmail.com
Sun Jun 18 03:26:16 CEST 2017


I created a new sequence A287878 for the trajectory of 234 under the map x
-> A230625(x) (234 is the smallest number whose destiny is presently
unknown). It needs a b-file.

For the analogous map x-> A048985(x), the entry A048986 says that all
numbers <= 2294 end at 1 or a prime,
but the destiny of 2295 is unknown. The trajectory of 2295 should probably
also be entered as a new sequence, with a b-file, in case anyone would like
to help.


Best regards
Neil

Neil J. A. Sloane, President, OEIS Foundation.
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com


On Fri, Jun 16, 2017 at 11:43 PM, David Seal <david.j.seal at gwynmop.com>
wrote:

> Thanks for the pointers to sequences I didn't know about - as you'll have
> seen, I've added some extra comments to some of them.
>
> Yes, 255987 is the only number I've found that is fixed in base 2, and
> 1007 <-> 1269 and 1503 <-> 3751 the only loops in base 2. That's in a
> search which I said went up to 6.5 * 10^8, but that was a typo: it should
> have been 6.5 * 10^9.
>
> I've since improved my search program significantly and am running it
> again on various bases, without so far finding any further solutions. The
> base 2 run has been going for somewhat over half a day and is currently up
> to about 1.95 * 10^10. Assuming no bugs in my program (always a dangerous
> assumption!), there are no other loops that are entirely below that limit,
> and therefore no other fixed values below it.
>
> A description of the program and the improvement: it runs upwards through
> possible 'top of loop' values. For each candidate value, it iteratively
> applies the CTAP ('Climb To A Prime') function until one of four things
> happens:
>
> * It reaches a prime.
>
> * It reaches a previously-discovered 'top of loop' value.
>
> * It reaches a number that exceeds the candidate value it started with.
>
> * It reaches the candidate value it started with.
>
> In the first three cases, it knows that the candidate value it started
> with isn't a 'top of loop' value and moves on to the next candidate, while
> in the fourth case, it's discovered a new 'top of loop' value.
>
> The improvement was that the original version simply looked at all
> integers as candidate 'top of loop' values, while the improved version uses
> the fact that such values must remain the same or decrease on the first
> step. The CTAP function is easily shown to have the property that if p1,
> p2, ... pn are distinct primes, then:
>
> CTAP(p1^k1 * p2^k2 * ... * pn^kn) >= CTAP(p1^k1) * CTAP(p2^k2) * ... *
> CTAP(pn^kn)
>
> with equality only if n=1 and CTAP(p1^k1) = p1^k1. So either the 'top of
> loop' value is a fixed value of the form p^k, or it must be divisible by at
> least one p^k for which CTAP(p^k) < p^k. So for each prime p, I determine
> the smallest k for which CTAP(p^k) < p^k (noting the cases of equality in
> the process), and I restrict the search to numbers that are multiples of at
> least one of those p^k (which can be done efficiently using a heap-based
> priority queue).
>
> In base 2, for example, that says that I only need look at candidates that
> are multiples of 2^5, 3^3 or p^2 for p >= 5. So the fraction of all
> integers that I can avoid looking at is:
>
> 31/32 * 26/27 * 24/25 * 48/49 * 120/121 * 168/169 * ...
>
> = 31/24 * 26/24 * (3/4 * 8/9 * 24/25 * 48/49 * 120/121 * 168/169 * ...)
>
> = 31/24 * 26/24 * 6/pi^2
>
> = about 0.8507
>
> Furthermore, the candidates that do get through that are more easily
> factorisable than average - in particular, there are no products of two
> large primes among them. Together, they add up to a very worthwhile speed
> improvement.
>
> > It would be interesting to see the list of numbers that don't reach 1 or
> a
> > prime.  That is, the numbers that are fixed (and composite), or go to a
> > composite fixed point, or go into a loop.  If you have this list, could
> you
> > submit it as a new sequence?
>
> My program didn't give me that information, but I've produced a modified
> version that does. Unfortunately, though, it's only given me one term of
> the new sequence...
>
> That term is 217, which enters the 1007 <-> 1269 loop after 3 steps:
>
> 217 = 7 * 31 = binary 111 * 11111 -> binary 11111111 = 255
> 255 = 3 * 5 * 17 = binary 11 * 101 * 10001 -> binary 1110110001 = 945
> 945 = 3^3 * 5 * 7 = binary 11^11 * 101 * 111 -> binary 1111101111 = 1007
>
> All other values up to 233 get to primes, but I have not yet been able to
> determine what happens to 234, beyond that it grows to >= 2^63. Whether it
> ends up at a prime, in one of the known loops, in some as-yet-unknown loop,
> or just growing forever, I don't know, and so I don't know whether it's in
> your proposed sequence or not.
>
> Values like 234 are not uncommon. I've looked at the numbers 1-10000, with
> the following results:
>
> 9808 numbers were 1 or got to primes
> 42 numbers enter loops (other than primes going to themselves)
> 150 numbers went to values >= 2^63 without being resolved
>
> What I can tell you is that your proposed sequence starts:
>
> 217, 234?, 255, 408?, 420?, 446, 545?, 558, 564?, 595?, 668?, 678?, 717,
> 735, 749?, 775, 777?, 830?, 844?, 861?, 882?, 904?, 918?, 945, 950?, 956?,
> 958, 1003?, 1007, ...
>
> where question marks indicate terms that might or might not actually be in
> the sequence.
>
> Best regards,
>
> David
>
>
> > On 15 June 2017 at 20:35 Neil Sloane <njasloane at gmail.com> wrote:
> >
> >
> > David Seal:  Nice work!
> >
> > It turns out that the base-2 version is already in the OEIS,
> > although without your counterexample, which I have now added.
> >
> > I also added some sequences that were missing, so the base-2 problem is
> now
> > described in the following 5 entries:
> > A230625 & A287874 for the basic map,
> > and, for what you reach when the map is
> > iterated, A230626, A230627, A287875.
> >
> > There is a slight awkwardness in A287875, because the escape clause,
> which
> > says we write -1 if we don't reach 1 or a prime, is tricky to deal with
> in
> > base 2.  So the escape clause is "a(n) = -1 in decimal if ...", and
> > otherwise "a(n) = the prime reached, or 1, written in binary".
> >
> > Did you check to see if 255987 is the smallest number that is fixed in
> base
> > 2?  I assume so, but it wasn't clear from your message.
> >
> > It would be interesting to see the list of numbers that don't reach 1 or
> a
> > prime.  That is, the numbers that are fixed (and composite), or go to a
> > composite fixed point, or go into a loop.  If you have this list, could
> you
> > submit it as a new sequence?
> >
> >
> > Best regards
> > Neil
> >
> > Neil J. A. Sloane, President, OEIS Foundation.
> > 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
> > Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
> > Phone: 732 828 6098; home page: http://NeilSloane.com
> > Email: njasloane at gmail.com
> >
> >
> > On Tue, Jun 13, 2017 at 9:31 AM, David Seal <david.j.seal at gwynmop.com>
> > wrote:
> >
> > > 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
> > >
> > > --
> > > Seqfan Mailing list - http://list.seqfan.eu/
> > >
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>



More information about the SeqFan mailing list