Problem aus Monoid. Heft 165, Seite 14¶

Definition¶

Gegeben:

$F(m) = m + A(m)$

$A(m)=m \text{ für } 1 \leq m \leq 9 $

Für $m \geq 10$ ist $A(m)$ das Produkt der Ziffern von $m$.

Es wird eine Kette $K_n$ gebildet, deren erstes Glied $n$ ist mit $n \in \mathbb{N}$ und die mindestens ein weiteres Glied $\neq n$ besitzt. $$F(5)=5+A(5)=5+5=10$$ $$F(123)=123+A(123)=123+6=129$$

weitere Definitionen¶

$$F(n)=F^1(n)$$ $$F(F(n))=F^2(n)$$ Daraus folgt: $$F^3(38)=F(F(F(38)))=102$$ $$K_{38}={38,62,74,102}$$ Wird festgestellt: $n$ kann keine nullhaltige Zahl sein. Die letzte Zahl der Kette ist immer nullhaltig.

Gesucht¶

Behauptung: Ketten $K_n$, mit $n < 1000$, mit mehr als 10 Gliedern sind selten.

Implementierung¶

In [1]:
import math

def A(m: int) -> int:
    if m < 10:
        return m
    return math.prod(map(int, str(m)))

def F(m: int) -> int:
    return m + A(m)

F(F(F((38))))
Out[1]:
102
In [2]:
def K(n: int) -> set[int]:
    chain = set()
    m = n
    while True:
        chain.add(m)
        new_m = F(m)
        if new_m in chain:
            break
        m = new_m
    if len(chain) < 2:
        raise Exception("K_n isn't allowed to have less than 2 elements")
    return chain

# Function returns a set, so it may not be sorted. K_n by definition is always getting bigger, but our implementation ignores that.
# For an actually accurate K_n chain you need to sort the set returned by K. I am not doing that here for obvious reasons.
K(38), len(K(38))
Out[2]:
({38, 62, 74, 102}, 4)

Untersuchung¶

In [3]:
count = 0
ns = []
ceiling = 1000
for n in range(1, ceiling + 1):
    try:
        k = K(n)
    except Exception:
        pass
    else:
        if len(k) > 10:
            ns.append(n)
            count += 1

# percentage
count / 1000
Out[3]:
0.043
In [4]:
ns[:10]
Out[4]:
[1, 187, 243, 246, 248, 254, 264, 267, 282, 294]
In [5]:
# Looking at the chains to confirm they have more than 10 members
K(1), K(187)
Out[5]:
({1, 2, 4, 8, 16, 22, 26, 38, 62, 74, 102},
 {187,
  243,
  267,
  351,
  366,
  474,
  586,
  826,
  922,
  958,
  1318,
  1342,
  1366,
  1474,
  1586,
  1826,
  1922,
  1958,
  2318,
  2366,
  2582,
  2742,
  2854,
  3174,
  3258,
  3498,
  4362,
  4506})
In [6]:
# rewrite the code so we can use it with other constraints
def count_K(maxChainLength: int, *, ceiling: int = 1000) -> tuple[int, list[set[int]]]:
    count = 0
    ks = []
    for n in range(1, ceiling + 1):
        try:
            k = K(n)
        except Exception:
            continue
        else:
            if len(k) == maxChainLength: # IMPORTANT!! we look at exactly stuff now
                count += 1
                ks.append(k)
    assert count == len(ks)
    return count, ks

 # 1.3% have exactly 10 elements
count_K(10)[0] / 1000
Out[6]:
0.013
In [7]:
cl = 2
cnts = []
fail_switch = 0
while True:
    cnt, _ = count_K(cl)
    if cnt == 0:
        fail_switch += 1
    if cnt == 0 and fail_switch == 100:
        break
    cnts.append((cl, cnt))
    cl += 1

cnts = list(filter(lambda x: x[1] != 0, cnts))
cnts
Out[7]:
[(2, 224),
 (3, 168),
 (4, 127),
 (5, 91),
 (6, 67),
 (7, 37),
 (8, 28),
 (9, 21),
 (10, 13),
 (11, 4),
 (12, 2),
 (16, 1),
 (17, 2),
 (18, 2),
 (19, 4),
 (20, 5),
 (21, 2),
 (22, 1),
 (23, 3),
 (24, 4),
 (25, 4),
 (26, 4),
 (27, 2),
 (28, 3)]
In [8]:
# most chains have 2 elements
max(cnts, key=lambda x: x[1])
Out[8]:
(2, 224)
In [9]:
# only one `n` has 13 - 22 elements
min(cnts, key=lambda x: x[1])
Out[9]:
(16, 1)
In [10]:
count_K(16)
Out[10]:
(1,
 [{898,
   1474,
   1586,
   1826,
   1922,
   1958,
   2318,
   2366,
   2582,
   2742,
   2854,
   3174,
   3258,
   3498,
   4362,
   4506}])
In [11]:
# longest chain has 28 elements.
max(cnts, key=lambda x: x[0])
Out[11]:
(28, 3)

Ergebnis¶

Für $n<1000$: Die meisten Ketten haben nur 2 Elemente. Die längste Kette hat 28 Elemente. $K(898)$ ist die einzige Kette mit genau 16 Elemente. Ketten mit mehr als 10 Elemente sind seltener als Ketten mit weniger als 10 Elemente.