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

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, 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, 9, 10, 8, 8, 10, 9, 9, 8, 7, 6, 10, 7, 10, 9, 10, 7, 9, 9, 9

Offset: 1

Author

Rémy Sigrist, Aug 23 2020

Keywords

• nonn
• base

Comments

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

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

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

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

- otherwise replace s by prime(s).

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

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

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

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

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

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

This sequence is well defined:

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

1

2 -> 1

3 -> 2 -> 1

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

5 -> 3 -> 2 -> 1

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

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

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

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

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

11 -> 5 -> 3 -> 2 -> 1

- so for any number n:

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

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

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

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

- and eventually we will reach 1.

Links

• Rémy Sigrist, PARI program for A337321

Crossrefs

Cf. A323286, A323454.

Programs

PARI

See Links section.

Formula

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