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

[Joseph Myers]

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