[seqfan] Re: Scott Shannon's "Grow" sequence A332580 (and A332584)
Joseph Myers
jsm at polyomino.org.uk
Thu Feb 20 17:25:56 CET 2020
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
More information about the SeqFan
mailing list