A337321 - OEIS

%I #8 Aug 24 2020 02:03:42

%S 0,1,2,10,3,7,9,10,8,10,4,5,6,8,7,9,8,9,9,9,5,6,7,8,8,10,7,10,9,10,5,

%T 6,7,7,8,9,6,9,10,8,7,8,7,9,8,9,8,9,8,10,6,7,8,8,9,10,7,10,9,11,8,9,9,

%U 9,10,8,8,10,9,9,8,7,6,10,7,10,9,10,7,9,9,9

%N a(n) is the least number of steps required to reach 1 starting from n under substring substitutions of the form k <-> prime(k) (where prime(k) denotes the k-th prime number).

%C This sequence is a variant of "Choix de Bruxelles" (where we consider substring substitutions of the form k <-> 2*k, see A323286):

%C - we map a positive number n to any number that can be obtained as follows:

%C - take a nonempty substring s (without leading zero) in the decimal representation of n,

%C - if the value of s corresponds to a prime number, say the k-th prime number, then replace s by k or by prime(s),

%C - otherwise replace s by prime(s).

%C For example, the number 17 can be mapped to any of those values:

%C - 27 (by replacing the leading 1 by prime(1) = 2),

%C - 14 (by replacing the trailing 7 = prime(4) by 4),

%C - 117 (by replacing the trailing 7 by prime(7) = 17),

%C - 7 (by replacing 17 = prime(7) by 7),

%C - 59 (by replacing 17 by prime(17) = 59).

%C This sequence is well defined:

%C - the sequence is well defined for any number <= 11 by considering the following (minimal) paths:

%C       1

%C       2 ->  1

%C       3 ->  2 ->  1

%C       4 ->  7 -> 17 ->  27 ->  37 -> 12 -> 11 -> 5 -> 3 -> 2 -> 1

%C       5 ->  3 ->  2 ->   1

%C       6 -> 13 -> 12 ->  11 ->   5 ->  3 ->  2 -> 1

%C       7 -> 17 -> 27 ->  37 ->  12 -> 11 ->  5 -> 3 -> 2 -> 1

%C       8 -> 19 -> 67 -> 137 -> 127 -> 31 -> 11 -> 5 -> 3 -> 2 -> 1

%C       9 -> 23 -> 13 ->  12 ->  11 ->  5 ->  3 -> 2 -> 1

%C      10 -> 20 -> 71 ->  41 ->  13 -> 12 -> 11 -> 5 -> 3 -> 2 -> 1

%C      11 ->  5 ->  3 ->   2 ->   1

%C - so for any number n:

%C      - we can transform any of its nonzero digit > 1 into a digit 1,

%C      - once we have a number with only 1's and 0's:

%C          - while this number is > 1, it either starts with "10" or with "11",

%C            and we can transform this prefix into a "1",

%C          - and eventually we will reach 1.

%H Rémy Sigrist, <a href="/A337321/a337321.gp.txt">PARI program for A337321</a>

%F a(prime(n)) <= 1 + a(n).

%o (PARI) See Links section.

%Y Cf. A323286, A323454.

%K nonn,base

%O 1,3

%A _Rémy Sigrist_, Aug 23 2020