Her boyutta ince?

Question

'Den hat Bu olumlu bir tam sayı çağrı, bu sorunun slimdownable veya ince her kendisi tarafından takip edilir bir tamsayı dizisinin bir parçası ise, kısa için bölünür uzunluğu basamak yani, sayı. Özellikle, her birinin uzunluğuna bölünebilir olması gerekir ve dizi, tek haneli bir sayıya ulaşıncaya kadar düşecektir.

Örnekler:

108: ince çünkü $108\overset{/3}{\rightarrow}36\overset{/2}{\rightarrow}18\overset{/2}{\rightarrow}9\overset{/1}{\circlearrowleft}$

78: zayıf değil çünkü $78\overset{/2}{\rightarrow}39\overset{/2}{\rightarrow}\Vert$

Herhangi bir pozitif tam sayı için bunu kanıtlayın veya reddedin $n$ ince bir sayı var $n$ rakamlar.

Not: Bir karşı örnek oluşturmak için veya örneğin asimptotik bir sonucu tamamlamak için veya uygun gördüğünüz her şeyi tamamlamak için bir bilgisayar kullanabilirsiniz. Bunu yapmayı seçerseniz, kodunuzu doğrulamak için lütfen aşağıdaki test sorularını yanıtlayın:

İle herhangi bir çözüm var mı $11111$rakamlar? Varsa: Kaç tane? Ortanca değerlerinin ilk 10 hanesi nedir?
Her biri için$n$ arasında $1$ ve $11111$ çözüm sayısını hesapla $n$rakamlar. En büyük sayı nedir?

Kodunuz için hızlı bir mantık kontrolü olarak kullanabileceğiniz bir test durumu:

3590 hanede dört çözüm vardır. Hepsi zayıflıyor$6$. Bu numaraların ilk on hanesi '3159252337 ...', '3735860235 ...', '4606981484 ...', '6706597705 ...' şeklindedir.

Answer 1

Sonuç:

Herhangi $n$-digit sayı, tüm pozitif tamsayılar için ince bir sayı olamaz $n$.

Muhakeme:

Hepsi için $n$, birden fazla olmalı $n$ yani $n$rakamlar uzun.

Hadi arayalım $n$-dijital numara $Z$.
Bunu hesaba katın$10^{ceil(log(n))}$ - bunu arayalım $a$, olmalı $a/n$ katları $n$. Bu, zayıflama sürecini aşağı indirmemizi sağlar.
Geri bakalım$Z$. Doğru olanı seçmemiz koşuluyla, önceki 2 adımda$Z$en az bir numara olacak $y$ uzunluk $(n-a)$ veya $(n-a+1)$ nerede $y = Z/n$ ve yeni bir ile ifade edilebilir $Z$ süreci tekrarlamak için.

Şimdi, 5-9'dan başlayarak (1-4 2 basamaklı bir sayı oluşturamadığından) ve Excel'in # Değer hatasına çarptığı yerde biten yeni değerler üreten bir Excel elektronik tablosunun gururlu sahibiyim.

Aşağıdaki resim azalan sıradadır (9 - 5)

Bende yiyen şey büyük $n$.

İçin $n$ = 1 milyar, zayıf bir sayı olacağını garanti edemem $n$1 milyar - 1 ile 1 milyar - 9 arasında, özellikle de sadece 5 başlangıç ​​yolum olduğu için.
Ve boşluk yalnızca daha geniş ve daha geniş olacağından$n\rightarrow\infty$, tüm pozitif tam sayılar için ince bir sayı olamaz$n$.

örneğin için$n$ = $1E1,000,000$, benim bölünmem ilk sayının 6 basamak düşmesine neden olur ve boşluğu sadece 5 deterministik yolla doldurabilirim, ama sonunda doldurulamaz.