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.

15, 23, 119, 167, 12049, 424, 735, 907, 17117, 1250, 307747, 2703, 49225, 9422, 57823, 5437, 2076131, 7747, 639987, 44960, 822799, 11537, 23809465, 24967, 1539917, 109346, 4643181, 26357, 5587832443, 37440, 1885949, 285085, 7782015, 265806, 1250473675, 66524, 8340541, 699890, 158607997, 85684

Offset: 2

Author

N. J. A. Sloane, Apr 04 2023, based on an email from Zachary DeStefano

Keywords

• nonn
• base

Comments

From Zachary DeStefano, May 17 2023: (Start)

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)

Examples

			To reach the digits 0 though 9 in base 10 from 17117:
 171*17 -> 290*7  -> 203*0 -> 0
 1711*7 -> 1197*7 -> 837*9 -> 7*533 -> 373*1 -> 37*3  -> 1*11 -> 1*1 -> 1
 171*17 -> 2*907  -> 1*814 -> 8*14  -> 1*12  -> 1*2   -> 2
 1*7117 -> 711*7  -> 49*77 -> 377*3 -> 113*1 -> 1*13  -> 1*3  -> 3
 171*17 -> 2*907  -> 1*814 -> 8*14  -> 11*2  -> 2*2   -> 4
 1711*7 -> 1197*7 -> 837*9 -> 75*33 -> 247*5 -> 1*235 -> 23*5 -> 1*15 -> 1*5  -> 5
 17*117 -> 19*89  -> 169*1 -> 16*9  -> 1*44  -> 4*4   -> 1*6  -> 6
 1711*7 -> 1197*7 -> 837*9 -> 7*533 -> 37*31 -> 11*47 -> 51*7 -> 3*57 -> 17*1 -> 1*7 -> 7
 17*117 -> 1*989  -> 98*9  -> 88*2  -> 1*76  -> 7*6   -> 4*2  -> 8
 1*7117 -> 711*7  -> 49*77 -> 377*3 -> 113*1 -> 11*3  -> 3*3  -> 9
		

Links

• Zachary DeStefano and Tim Peters, Table of n, a(n) for n = 2..119
• Michael S. Branicky, Python program
• Michael De Vlieger, Plot of digit d in sequence S_n(m) in black at (x, y) = (m, d) 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.
• Zachary DeStefano and Tim Peters, Known terms and bounds

Crossrefs

Cf. A361337-A361349.

Programs

Mathematica

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

Python

from itertools import count
from sympy.ntheory import digits
from functools import lru_cache
def fd(d, b): # from_digits
    return sum(di*b**i for i, di in enumerate(d[::-1]))
@lru_cache(maxsize=None)
def f(n, b):
    if n < b: return {n}
    s = digits(n, b)[1:]
    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)}
def a(n, printat=False):
    return next(k for k in count(1) if len(f(k, n))==n)
print([a(n) for n in range(2, 18)]) # Michael S. Branicky, Apr 04 2023

Python

# see link for a version that is faster and uses less memory

Extensions

a(21)-a(29) from Michael S. Branicky, Apr 04 2023

a(30)-a(41) from Zachary DeStefano, Apr 05 2023