cp's OEIS Frontend

A361340 a(n) = smallest number with the property that the split-and-multiply technique (see A361338) in base n can produce all n single-digit numbers.

%I A361340 #53 Dec 18 2023 08:29:08
%S A361340 15,23,119,167,12049,424,735,907,17117,1250,307747,2703,49225,9422,
%T A361340 57823,5437,2076131,7747,639987,44960,822799,11537,23809465,24967,
%U A361340 1539917,109346,4643181,26357,5587832443,37440,1885949,285085,7782015,265806,1250473675,66524,8340541,699890,158607997,85684
%N A361340 a(n) = smallest number with the property that the split-and-multiply technique (see A361338) in base n can produce all n single-digit numbers.
%C A361340 From _Zachary DeStefano_, May 17 2023: (Start)
%C A361340 There is a strong linear relationship between n^(n / phi(n)) and a(n) (see A000010 for phi(n)) which results from the final digit falling into subgroups of Z/nZ during split-and-multiply steps. This explains why a(n) is significantly smaller for prime n and significantly larger when n contains several small prime factors (ex. 2 * 3 * 5 = 30) (End)
%H A361340 Zachary DeStefano and Tim Peters, <a href="/A361340/b361340.txt">Table of n, a(n) for n = 2..119</a>
%H A361340 Michael S. Branicky, <a href="/A361340/a361340.py.txt">Python program</a>
%H A361340 Michael De Vlieger, <a href="/A361340/a361340.png">Plot of digit d in sequence S_n(m) in black at (x, y) = (m, d)</a> for bases n = 2..12 as labeled, m = 1..1000, and digits d = 0..n-1, 12X exaggeration. This sequence shows the first occasion of a vertical black bar in base n.
%H A361340 Zachary DeStefano and Tim Peters, <a href="/A361340/a361340_2.txt">Known terms and bounds</a>
%e A361340 To reach the digits 0 though 9 in base 10 from 17117:
%e A361340  171*17 -> 290*7  -> 203*0 -> 0
%e A361340  1711*7 -> 1197*7 -> 837*9 -> 7*533 -> 373*1 -> 37*3  -> 1*11 -> 1*1 -> 1
%e A361340  171*17 -> 2*907  -> 1*814 -> 8*14  -> 1*12  -> 1*2   -> 2
%e A361340  1*7117 -> 711*7  -> 49*77 -> 377*3 -> 113*1 -> 1*13  -> 1*3  -> 3
%e A361340  171*17 -> 2*907  -> 1*814 -> 8*14  -> 11*2  -> 2*2   -> 4
%e A361340  1711*7 -> 1197*7 -> 837*9 -> 75*33 -> 247*5 -> 1*235 -> 23*5 -> 1*15 -> 1*5  -> 5
%e A361340  17*117 -> 19*89  -> 169*1 -> 16*9  -> 1*44  -> 4*4   -> 1*6  -> 6
%e A361340  1711*7 -> 1197*7 -> 837*9 -> 7*533 -> 37*31 -> 11*47 -> 51*7 -> 3*57 -> 17*1 -> 1*7 -> 7
%e A361340  17*117 -> 1*989  -> 98*9  -> 88*2  -> 1*76  -> 7*6   -> 4*2  -> 8
%e A361340  1*7117 -> 711*7  -> 49*77 -> 377*3 -> 113*1 -> 11*3  -> 3*3  -> 9
%t A361340 Table[Catch[Monitor[Do[(Set[c, Count[Union@Flatten[#], _?(# < b &)]]; If[c == b, Throw[i]]) &@ NestWhileList[Flatten@ Map[Function[w, Array[If[And[#[[-1, 1]] == 0, Length[#[[-1]]] > 1], Nothing, Times @@ Map[FromDigits[#, b] &, #]] &@ TakeDrop[w, #] &, Length[w] - 1]][IntegerDigits[#, b]] &, #] &, {i}, Length[#] > 0 &], {i, 0, Infinity}], {b, i, c}]], {b, 2, 6}] (* _Michael De Vlieger_, Apr 04 2023, with Monitor to show progress *)
%o A361340 (Python)
%o A361340 from itertools import count
%o A361340 from sympy.ntheory import digits
%o A361340 from functools import lru_cache
%o A361340 def fd(d, b): # from_digits
%o A361340     return sum(di*b**i for i, di in enumerate(d[::-1]))
%o A361340 @lru_cache(maxsize=None)
%o A361340 def f(n, b):
%o A361340     if n < b: return {n}
%o A361340     s = digits(n, b)[1:]
%o A361340     return {e for i in range(1, len(s)) if s[i]!=0 or i==len(s)-1 for e in f(fd(s[:i], b)*fd(s[i:], b), b)}
%o A361340 def a(n, printat=False):
%o A361340     return next(k for k in count(1) if len(f(k, n))==n)
%o A361340 print([a(n) for n in range(2, 18)]) # _Michael S. Branicky_, Apr 04 2023
%o A361340 (Python) # see link for a version that is faster and uses less memory
%Y A361340 Cf. A361337-A361349.
%K A361340 nonn,base
%O A361340 2,1
%A A361340 _N. J. A. Sloane_, Apr 04 2023, based on an email from _Zachary DeStefano_
%E A361340 a(21)-a(29) from _Michael S. Branicky_, Apr 04 2023
%E A361340 a(30)-a(41) from _Zachary DeStefano_, Apr 05 2023