login
A241180
Start with n; add to it any of its digits; repeat; a(n) = minimal number of steps needed to reach a prime greater than n.
12
1, 4, 3, 3, 2, 2, 3, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 6, 6, 1, 5, 3, 4, 2, 3, 1, 5, 1, 6, 2, 2, 5, 1, 2, 4, 4, 1, 3, 4, 3, 4, 1, 3, 2, 3, 2, 2, 1, 5, 2, 2, 2, 1, 4, 1, 4, 3, 3, 3, 1, 3, 3, 3, 1, 2, 1, 2, 4, 4, 2, 1, 2, 2, 4, 1, 3, 3, 3, 4, 1, 3, 3, 2, 3, 2, 2
OFFSET
1,2
COMMENTS
Is it a theorem that a(n) aways exists?
Yes: as long as nonzero digits are used, eventually you reach a number x starting with 10, large enough that there is a prime between x and 3*x/2. All the numbers from x to 3*x/2 start with 1, so if you use the digit 1 you will eventually reach a prime. - Robert Israel, Mar 17 2019
A variant of this (A241181) sets a(n) = 0 if n is already a prime.
REFERENCES
Eric Angelini, Posting to Sequence Fans Mailing List, Apr 20 2014
LINKS
EXAMPLE
Examples, in condensed notation:
1+1=2
2+2=4+4=8+8=16+1=17
3+3=6+6=12+1=13
4+4=8+8=16+1=17
5+5=10+1=11
6+6=12+1=13
7+7=14+4=18+1=19
8+8=16+1=17
9+9=18+1=19
10+1=11
11+1=12+1=13
12+1=13
13+3=16+1=17
14+4=18+1=19
15+1=16+1=17
16+1=17
17+1=18+1=19
18+1=19
19+9=28+8=36+3=39+9=48+8=56+5=61
20+2=22+2=24+2=26+6=32+2=34+3=37
...
MAPLE
g:= proc(n, Nmax) option remember; local L, d, t;
if isprime(n) then return 0 fi;
if n > Nmax then return infinity fi;
L:= convert(convert(n, base, 10), set) minus {0};
1 + min(seq(procname(n+d), d=L));
end proc:
f:= proc(n, Nmax) local L, d, t;
L:= convert(convert(n, base, 10), set) minus {0};
1 + min(seq(g(n+d, Nmax), d=L))
end proc:
map(f, [$1..200], 1000); # Robert Israel, Mar 17 2019
MATHEMATICA
A241180[n_] := Module[{c, nx},
c = 1; nx = n;
While[ !
AnyTrue[nx = Flatten[nx + IntegerDigits[nx]],
PrimeQ [#] && # > n &], c++];
Return[c]];
Table[A241180[i], {i, 100}] (* Robert Price, Mar 17 2019 *)
CROSSREFS
KEYWORD
easy,nonn,base
AUTHOR
N. J. A. Sloane, Apr 23 2014
EXTENSIONS
a(23)-a(87) from Hiroaki Yamanouchi, Sep 05 2014
STATUS
approved