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

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

Table of n, a(n) for n=1..82.

Rémy Sigrist, PARI program for A337321

Formula

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

Prog

(PARI) See Links section.

Crossrefs

Cf. A323286, A323454.

Sequence in context: A060466 A243992 A317549 * A342047 A239083 A239084

Adjacent sequences: A337318 A337319 A337320 * A337322 A337323 A337324

Keyword

nonn,base

Author

Rémy Sigrist, Aug 23 2020

Status

approved