cp's OEIS Frontend

A332580 a(n) = minimal positive k such that the concatenation of the decimal digits of n,n+1,...,n+k is divisible by n+k+1, or -1 if no such k exists.

%I A332580 #151 Feb 10 2025 03:13:39
%S A332580 1,80,1885,6838,1,44,13,2,1311,18,197,20,53,134,993,44,175,124518,263,
%T A332580 26,107,10,5,62,15,33172,9,14,317,708,1501,214,37,34,67,270,19,20188,
%U A332580 78277,10738,287,2390,695,2783191412912,3,700,8303,350,21,100,2249,21326
%N A332580 a(n) = minimal positive k such that the concatenation of the decimal digits of n,n+1,...,n+k is divisible by n+k+1, or -1 if no such k exists.
%C A332580 Certainly n+k must be even, since no odd number can be divisible by an even number.
%C A332580 The values of n+k = n+a(n) are given in the companion sequence A332584.
%C A332580 A heuristic argument suggests that k should always exist.
%C A332580 As of Jul 10 2020, up to n = 1000 there are just two unknown values, a(158) and a(539).
%C A332580 The following remarks summarize program made during the first half of 2020.
%C A332580 On Feb 19 2020 _Joseph Myers_ discovered that a(98) = 259110640. On Feb 20 2020 he reported that a(44) > 10^11 if it exists; a(92), a(158) and a(170) are all > 10^10 if they exist; a(494), a(539), a(563), a(761), a(854), a(944) and a(956) are all > 2*10^9 if they exist; and that he has found all the other values up to a(1000). - _N. J. A. Sloane_, Feb 23 2020.
%C A332580 Added Feb 26 2020: _Joseph Myers_ has now checked all the numbers up to 1000 out to a limit of 10^11 (see link).
%C A332580 Update from _Paul Zimmermann_, Mar 17 2020: (Start)
%C A332580 I started a parallel program using the same algorithm as in _Joseph Myers_'s "grow.c" program on the few sequences with unknown status in http://oeis.org/A332580/a332580_2.txt.
%C A332580 This program just found:
%C A332580 pzimmermann@wurst:~/A332580$ tail 956.out
%C A332580 n=956 kmax=200000000000
%C A332580 found k=162236437060
%C A332580 It thus seems that a(956) = 162236437060, i.e., the term of index n+k+1 is divisible by 162236438017 = 43 * 5051 * 746969. (End)
%C A332580 Partial confirmation from _Scott R. Shannon_, Mar 17 2020:  I set n = 956 and a k value a few less than 162236437060 in my Java version of Joseph Myer's program, and it found the results Paul Zimmermann gave. But that’s not much of a confirmation as it uses the same algorithm, just implemented in a different language.
%C A332580 Partial confirmation from Pierrick Gaudry, Mar 18 2020:  (Start)
%C A332580 I ran the attached small C program in order to check that a(956) = 162236437060. More precisely, I check only that the 162236437060-th integer obtained starting with 956 is indeed 0 modulo 162236438017.
%C A332580 For this there is no need to rely on multi-precision arithmetic. However, since 162236438017 > 2^32, it is not possible to use 64-bit arithmetic; or at least, it was easier to use the 128-bit arithmetic provided by the compiler.
%C A332580 The algorithm is then fairly simple: just compute iteratively the big number obtained by concatenating 956, 957, 958, ... and so on, and reduce all along the way modulo 162236438017. The result should be zero. This was tested on a few other known example.
%C A332580 After a bit more than 1 hour on my laptop, this indeed prints 0, thus confirming that a(956) <= 162236437060 (this simple method does not check if there is a smaller value). (End)
%C A332580 Full confirmation for a(956) from _Joseph Myers_, Mar 18 2020: I restarted computations for 956 where I had stopped them before (at 101 * 10^9) and ran them up to 163 * 10^9; I also get 162236437060.
%C A332580 Update from _Paul Zimmermann_, Mar 22 2020: (Start)
%C A332580 Here are four more values to check, confirmed independently by Pierrick Gaudry:
%C A332580 a(44) <= 2783191412912
%C A332580 a(92) <= 218128159460
%C A332580 a(494) <= 2314160375788
%C A332580 a(854) <= 440578095296 (also k=587470935254 divides)
%C A332580 All four values were found with the "sieving" algorithm I described in an earlier email (see the Alekseyev et al. paper), sieving all primes up to 5000000000. Thus it is possible that smaller solutions exist.
%C A332580 Up to n=1000, the remaining cases where we have no bound at present are 158, 539, 761, 944. (End)
%C A332580 a(761) <= 111508066823971. Now only 3 values remain up to n=1000 (158, 539, 944). _Paul Zimmermann_, Mar 23 2020
%C A332580 I restarted my exhaustive search for 92 where I had previously stopped it, and can confirm a(92) = 218128159460.  - _Joseph Myers_, Mar 23 2020
%C A332580 The remaining values to check are:
%C A332580 a(44)  <= 2783191412912, a(494) <= 2314160375788, a(761) <= 111508066823971, a(854) <= 440578095296. - _Paul Zimmermann_, Mar 24 2020
%C A332580 a(854) = 440578095296 confirmed by _Joseph Myers_ on Mar 26 2020.
%C A332580 Summary: As of Apr 15 2020, a(n) is known for all n <= 1000 except for four values where we have only an upper bound (44, 494, 539, and 761), and two values (158, 944) where all we know is that if k exists then it is greater than 10^15. See the table in the Links section. - _Joseph Myers_ and _Paul Zimmermann_.
%C A332580 From _Paul Zimmermann_, Apr 17 2020: I have completed the full check for n=494 up to n+k=10^12. Thus a(494) >= 10^12-494. It took about 4 hours. The final check from 10^12 to 2314160375788+494+1 should take another 4-5 hours.  (I don't want this comment to be lost, even though it will probably be replaced by something stronger very soon. - _N. J. A. Sloane_, Apr 17 2020)
%C A332580 From _Paul Zimmermann_, Apr 18 2020: (Start)
%C A332580 I confirm that a(44) = 2783191412912 and a(494) = 2314160375788. These were checked with a parallel version of Joseph's program (attached). For n=44 I ran the following script which submits 28 jobs checking each a range of 10^11 values:
%C A332580 for i in `seq 0 27`; do
%C A332580    kmin=`expr 1 + $i \* 100000000000`
%C A332580    kmax=`expr $kmin + 100000000000 - 1`
%C A332580    oarsub -p "cluster='grvingt'" -q production -l walltime=5 "./A332580 -kmin $kmin 44 $kmax"
%C A332580 done
%C A332580 The last job took a little less than 4 hours (wall clock time) on a 32-core cpu (64 virtual cores), thus it took a total of about 300 cpu days. (End)
%C A332580 a(944) <= 1032422879252. - _Paul Zimmermann_, Apr 19 2020
%H A332580 Joseph Myers and Paul Zimmermann, <a href="/A332580/b332580.txt">Table of n, a(n) for n = 1..157</a>
%H A332580 M. A. Alekseyev, J. S. Myers, R. Schroeppel, S. R. Shannon, N. J. A. Sloane, and P. Zimmermann, <a href="http://arxiv.org/abs/2004.14000">Three Cousins of Recaman's Sequence</a>, Fibonacci Quart. 60:3 (2022), 201-219 (preprint arXiv:2004:14000 [math.NT], 2021).
%H A332580 Pierrick Gaudry, <a href="/A332580/a332580.c.txt">C program for partial check</a>
%H A332580 Joseph Myers and Paul Zimmermann, <a href="/A332580/a332580_4.txt">Table of n, a(n) for n <= 1000</a>. The single remaining UNKNOWN entry at n = 158 either -1 or greater than 10^14.
%H A332580 N. J. A. Sloane, <a href="https://vimeo.com/457349959">Conant's Gasket, Recamán Variations, the Enots Wolley Sequence, and Stained Glass Windows</a>, Experimental Math Seminar, Rutgers University, Sep 10 2020 (video of Zoom talk).
%H A332580 Paul Zimmermann, <a href="/A332580/a332580_1.c.txt">A parallel version of Joseph's C program</a>
%e A332580 a(1) = 1 as '1' || '2' = '12', which is divisible by 3 (where || denotes decimal concatenation).
%e A332580 a(2) = 80: the concatenation 2 || 3 || ... || 82 is
%e A332580   23456789101112131415161718192021222324252627282930313233343536373839\
%e A332580   40414243444546474849505152535455565758596061626364656667686970717273747\
%e A332580   576777879808182, which is divisible by 83.
%e A332580 a(7) = 13 as '7' || '8' || '9' || '10' || '11' || '12' ||  ... || '20' = 7891011121314151617181920, which is divisible by 21.
%e A332580 a(8) = 2 as '8' || '9' || '10' = 8910, which is divisible by 11.
%p A332580 grow := proc(n,M) # searches out to a limit of M, returns [n,n+k] or [n,-1] if no k was found
%p A332580   local R,i;
%p A332580   R:=n;
%p A332580   for i from n+1 to M do
%p A332580     R:=R*10^length(i)+i;
%p A332580     if (i mod 2) = 0 then
%p A332580       if (R mod (i+1)) = 0 then return([n, i]); fi;
%p A332580     fi;
%p A332580   od:
%p A332580   [n, -1];
%p A332580 end;
%p A332580 for n from 1 to 100 do lprint(grow(n,20000)); od;
%o A332580 (PARI) apply( {a(n,L=10^logint(n*10,10),c=n)= n%2||c=c*L+n+1; for(k=n+++n%2,oo, k<L||L*=10;(c=c*L+k)%k++||return(k-n);c=c*L+k)}, [1..17]) \\ Would take a few seconds for a(18). Without considering parity of k, code is simpler but about 50% slower. - _M. F. Hasler_, Feb 20 2020
%Y A332580 Cf. A061836 (multiplication instead of concatenation), A281232, A332584, A332585 (length of the final concatenation). See A058183 for finding the length of a concatenation.
%Y A332580 For records see A333546, A333547.
%Y A332580 For n=44, see A332562.
%Y A332580 See A332563, A332586 for a base 2 version.
%Y A332580 See A281232 for the positions of the 1's.
%Y A332580 A029455 is an older sequence in the same spirit.
%K A332580 nonn,base
%O A332580 1,2
%A A332580 _Scott R. Shannon_ and _N. J. A. Sloane_, Feb 16 2020
%E A332580 Edited by _Max Alekseyev_, Dec 26 2024