Sind Zahlen, in denen alle Teilzeichenfolgen Primzahlen sind, unabhängig von der Basis endlich?

Ohne besonderen Grund bin ich auf die Folge/Menge aller Zahlen gestoßen, bei der alle Teilstrings der Dezimaldarstellung Primzahlen sind (A085823). Es ist leicht zu sehen, dass dies eine endliche Menge sein muss. Mein Ansatz war, dass sich die Ziffern irgendwann zwischen 3 und 7 ändern müssen (da eine Primzahl nicht mit 2 oder 5 enden kann, wenn sie größer ist, und eine Primzahl nicht nur aus zwei Nicht-1-Ziffern bestehen kann, wären diese durch 2 teilbar , 5 oder 11) und wir können sehen, wo es endet.

Aber wenn wir die Basis ändern, schlägt dieser Ansatz fehl. Zum Beispiel kann eine Primzahl zur Basis 8 auf 3, 5 oder 7 AFAICS enden, also können solche Zahlen in einer wechselnden Folge von 3, 5 und 7 enden, aber wenn man drei Ziffern hat, zwischen denen man wechseln kann, gibt es immer eine Möglichkeit, die Folge zu variieren.

Ich habe versucht, ein Python-Snippet zu schreiben, um solche Zahlen in verschiedenen Basen zu erzeugen, und für diejenigen, die ich getestet habe, scheint das Programm zu hängen (dh scheint keine Zahlen mehr zu finden). Stimmt es, dass es für jede Basis nur endlich viele solcher Zahlen gibt?

Antworten (1)

Ja!

Lassen B ≥ 2 eine Basis sein, in der Sie diese Zahlen darstellen möchten. Dann einstellen C := B − 1 . Deutlich, B ≡ 1 Mod C .

Nehmen wir nun an, es gäbe eine Zahl N was eine Länge hat ≥ 2 C + 1 für die jedes Teilwort seiner Darstellung in Basis ist B wäre wieder spitze. Schreiben N als A M ⋯ A 0 in der Basis B . In Betracht ziehen

S k :≡ ∑ ich = 0 k A ich Mod ⁡ C
für k ∈ { 0 , … , M } . Seit der S k kann nur nehmen C mögliche Werte u M + 1 ≥ 2 C + 1 nach Annahme haben wir, dass es gibt ich < J < k , ich , J , k ∈ { 0 , … , M } st S ich = S J = S k . Aber das impliziert k > ich + 1 Und:
0 ≡ S k − S ich ≡ ∑ l = ich + 1 k A l ≡ ∑ l = ich + 1 k A l ⋅ B l − ( ich + 1 ) Mod ⁡ C
Aber die letzte Summe davon nehmen wir Mod ⁡ C ist genau die Zahl dargestellt durch A k ⋯ A ich + 1 in der Basis B . Als Unterwort unserer N , es muss prim sein. Die obige Gleichheit ergibt dann, dass es eigentlich gleich sein muss C (da es teilbar ist durch C und Prim). Aber seit k > ich + 1 , wir haben
C = B − 1 = ∑ l = ich + 1 k A l ⋅ C l − ( ich + 1 ) ≥ A k ⋅ B k − ( ich + 1 ) > B
was ein Widerspruch ist.

Daraus können wir schließen, dass die Länge eines solchen N kann sein 2 C maximal. Es gibt also nur endlich viele solcher N s in jeder Basis.

Man kann sogar zeigen, dass die Länge höchstens ist 2 P − 1 Wo P ist die kleinste Primzahl, die sich nicht teilt B . Bei Interesse verlinke ich einen Beweis dafür.

Ein kleiner Punkt ist das da 0 Und 1 kann nicht in der Zeichenfolge sein, Sie können eine Basis wählen B > 2 . Ansonsten z B = 2 , Du hast dein C = 1 . Ansonsten sieht alles andere gut aus.
Mich würde die interessieren 2 P − 1 Beweis Jakob B.
Egal, ich habe es hinbekommen.
Sind Zahlen, in denen alle Teilzeichenfolgen Primzahlen sind, unabhängig von der Basis endlich?
AntwortenHierDatenschutz-Bestimmungen1y, 0v