cp's OEIS Frontend

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

%I A337321 #8 Aug 24 2020 02:03:42
%S A337321 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 A337321 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 A337321 9,10,8,8,10,9,9,8,7,6,10,7,10,9,10,7,9,9,9
%N 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).
%C A337321 This sequence is a variant of "Choix de Bruxelles" (where we consider substring substitutions of the form k <-> 2*k, see A323286):
%C A337321 - we map a positive number n to any number that can be obtained as follows:
%C A337321 - take a nonempty substring s (without leading zero) in the decimal representation of n,
%C A337321 - 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 A337321 - otherwise replace s by prime(s).
%C A337321 For example, the number 17 can be mapped to any of those values:
%C A337321 - 27 (by replacing the leading 1 by prime(1) = 2),
%C A337321 - 14 (by replacing the trailing 7 = prime(4) by 4),
%C A337321 - 117 (by replacing the trailing 7 by prime(7) = 17),
%C A337321 - 7 (by replacing 17 = prime(7) by 7),
%C A337321 - 59 (by replacing 17 by prime(17) = 59).
%C A337321 This sequence is well defined:
%C A337321 - the sequence is well defined for any number <= 11 by considering the following (minimal) paths:
%C A337321       1
%C A337321       2 ->  1
%C A337321       3 ->  2 ->  1
%C A337321       4 ->  7 -> 17 ->  27 ->  37 -> 12 -> 11 -> 5 -> 3 -> 2 -> 1
%C A337321       5 ->  3 ->  2 ->   1
%C A337321       6 -> 13 -> 12 ->  11 ->   5 ->  3 ->  2 -> 1
%C A337321       7 -> 17 -> 27 ->  37 ->  12 -> 11 ->  5 -> 3 -> 2 -> 1
%C A337321       8 -> 19 -> 67 -> 137 -> 127 -> 31 -> 11 -> 5 -> 3 -> 2 -> 1
%C A337321       9 -> 23 -> 13 ->  12 ->  11 ->  5 ->  3 -> 2 -> 1
%C A337321      10 -> 20 -> 71 ->  41 ->  13 -> 12 -> 11 -> 5 -> 3 -> 2 -> 1
%C A337321      11 ->  5 ->  3 ->   2 ->   1
%C A337321 - so for any number n:
%C A337321      - we can transform any of its nonzero digit > 1 into a digit 1,
%C A337321      - once we have a number with only 1's and 0's:
%C A337321          - while this number is > 1, it either starts with "10" or with "11",
%C A337321            and we can transform this prefix into a "1",
%C A337321          - and eventually we will reach 1.
%H A337321 Rémy Sigrist, <a href="/A337321/a337321.gp.txt">PARI program for A337321</a>
%F A337321 a(prime(n)) <= 1 + a(n).
%o A337321 (PARI) See Links section.
%Y A337321 Cf. A323286, A323454.
%K A337321 nonn,base
%O A337321 1,3
%A A337321 _Rémy Sigrist_, Aug 23 2020