[seqfan] Re: Scott Shannon's "Grow" sequence A332580 (and A332584)

Neil Sloane njasloane at gmail.com
Mon Feb 24 05:26:54 CET 2020


Dear Joseph,  Sorry for being silent for 3 days.

You said: "a(44) > 10^11 if it exists; a(92), a(158) and a(170) all > 10^10
if they
exist; a(494), a(539), a(563), a(761), a(854), a(944) and a(956) all >
2*10^9 if they exist; and I have all the other values up to a(1000)"

This is very impressive!  Could you send me a file up to 1000, with maybe
something like
"If it exists, at least X" for the missing entries?
Then I will add it to the sequences A332580 and A332584.

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 Thu, Feb 20, 2020 at 11:26 AM Joseph Myers <jsm at polyomino.org.uk> wrote:

> On Thu, 20 Feb 2020, Neil Sloane wrote:
>
> > Joseph, obviously you aren't doing a brute force search.  Could your
> > method of attack be modified as follows: suppose there is a solution, not
> > minimal, just a solution,
> > with say 14 digits. Let G = the Giant Prefix cat(44,45,...,10^13-1), then
> > set up the obvious recurrence
> > T_{i+1} = 10^14 * T_i + i, starting with T_0 = G. We want a T_i that is
> > divisible by 10^13+i+1, so to study that
> > we work over the ring Z/(10^13+i+1) Z - and reduce everything in sight
> mod
> > that number.
>
> I'm working mod n+k+1, and checking each possible value of k (after
> excluding those where n+k+1 is even, a multiple of 5, or a multiple of 3
> in the case where n is 2 mod 3, which can't work for obvious reasons).
> The key thing is to implement things in a way that takes time polynomial
> in log(k) rather than linear in k to check a particular value of k.
> Specifically, the concatenation of A consecutive numbers with B decimal
> digits each has the form (C*10^(AB) - D)/(10^B - 1)^2, where C and D are
> small numbers that can readily be explicitly computed, and 10^(AB) can be
> computed to a given modulus in time polynomial in log(AB), so compute it
> mod (n+k+1)(10^B - 1)^2 and then do the division above to get the required
> value mod n+k+1 (and repeat this process for each value of B from the
> number of digits in n to the number of digits in n+k to get the required
> number mod n+k+1).  (With this approach, the checks for different values
> of k are independent, so you can also check different ranges of k in
> parallel.)
>
> a(44) > 10^11 if it exists; a(92), a(158) and a(170) all > 10^10 if they
> exist; a(494), a(539), a(563), a(761), a(854), a(944) and a(956) all >
> 2*10^9 if they exist; and I have all the other values up to a(1000).
>
> --
> Joseph S. Myers
> jsm at polyomino.org.uk
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>



More information about the SeqFan mailing list