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.

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

Author

N. J. A. Sloane, Apr 23 2014

Keywords

• easy
• nonn
• base

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.

Examples

			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
...
		

References

• Eric Angelini, Posting to Sequence Fans Mailing List, Apr 20 2014

Links

• Hiroaki Yamanouchi, Table of n, a(n) for n = 1..100000

Crossrefs

Related sequences: A241173, A241174, A241175, A241176, A241177, A241178, A241179, A241180, A241181, A241182, A241183.

Programs

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 *)

Extensions

a(23)-a(87) from Hiroaki Yamanouchi, Sep 05 2014