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

Sean A. Irvine sairvin at gmail.com
Sun Jun 18 04:30:59 CEST 2017


I'm seeing a prime at step 104.  I'll make a b-file.

On 18 June 2017 at 13:26, Neil Sloane <njasloane at gmail.com> wrote:

> 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/
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>



More information about the SeqFan mailing list