Bez jednej
Uprzedzam na wstępie, że tym razem będzie bardziej matematycznie niż łamigłówkowo, a co gorsza – niełatwo.
W Encyklopedii ciągów liczbowych trafiłem na ciąg z gatunku dziwacznych, zaczynający się tak:
100, 105, 108, 110, 120, 121, 130, 132, 135, 140, 143, 150, 154, 160, 165, 170, 176, 180, 187, 190, 192, 195, 198, 200,…
Obejmuje on tzw. gapful numbers, czyli w wolnym tłumaczeniu „liczby szczerbate”. Chodzi o to, że pierwsza i ostatnia cyfra każdej liczby tworzą jej dwucyfrowy dzielnik. Można też tę własność w odniesieniu do początkowego fragmentu, czyli liczb 3-cyfrowych, określić trochę inaczej: jeśli z danej liczby usunąć środkowy „ząbek”, to pozostanie jej dzielnik.
W związku z „ząbkiem” postanowiłem ten egzemplarz nieco zmodyfikować, czyli zaproponować ciąg bliźniaczy, obejmujący liczby zdefiniowane tak:
każda zmienia się w swój dzielnik po usunięciu jednej cyfry z wnętrza (czyli nie pierwszej i nie ostatniej, bo szczerba musi być widoczna między ząbkami).
Początek tego ciągu – nazwijmy go 1-szczerbatym – jest taki, jak szczerbatego, ale od liczb 4-cyfrowych zaczynają się różnice, bo np. 1001 dzieli się przez 11, a przez 101 nie; najmniejsza 1-szczerbata liczba 4-cyfrowa większa od 1000 to 1050=150×7. Ciąg 1-szczerbaty jest więc znacznie rzadszy od szczerbatego (większe odstępy między wyrazami). Na pewno jest nieskończony, bo zawiera wszystkie liczby z dwoma zerami na końcu (usuwane jest przedostatnie zero). Czy liczb zakończonych tylko jednym zerem też jest w nim nieskończenie wiele (podobnie jak zapewne liczb bliźniaczych wśród pierwszych)? – tego nie jestem pewien. Wiem natomiast, że liczby nie kończące się zerem w pewnym momencie się kończą. Jaka jest największa z nich?
Zadanie da się rozwiązać matematycznie „na piechotę”, choć jest trudne, więc ciekaw jestem, czy ktoś sobie z nim poradzi. Oczywiście w konkurencji programistycznej także można startować.
Komentarze
Znalazłam taką szczerbatkę:
6075 : 675
ale największa ze wszystkich to ona pewnie nie jest.
Pozdrav z Malej Upy 🙂
Tyż piknie, ale jednak cztery cyferki to przykrótko.
Pięć zresztą także (np. 43875/4875=9).
Pozdravy z velkej Štavnicy 🙂
mp
Założyłem, że liczba będzie postaci 1Yxx…xx i będzie podzielna przez 1Y – 1. Czyli mamy:
N = 1Yxx…xx = (1Y-1) * 1xx…xx
N = (N – (1Y-1) * 10^m) * (1Y-1)
Po przekształceniu:
N = 10^m * (1Y-1)^2 / (1Y-2)
Pozostało znaleźć Y i dopasować m tak, aby liczba nie miała 0 na końcu.
(1Y-1)^2 / (1Y-2) daje skończone rozwinięcie dla Y = 2 i dla Y = 8
Dla Y = 2 wychodzi N = 10^m * 12,1 = 121
Dla Y = 8: N = 10^m * 18,0625 = 180625 = 17 * 10625
Podobne równanie można ułożyć przy innych założeniach, np. 1Yxx…xx podzielne przez 1Y-2. Dostajemy:
N = 10^m * (1Y-1) * (1Y-2) / (1Y-3)
Wyniki: 1125, 132, 19125
Ogólniej: ABxx…xx podzielne przez C
N = (AB-A) * C / (C-1) * 10^m
Tym sposobem nie znalazłem żadnej większej liczby niż 180625.
Pozostają do sprawdzenia przypadki, gdzie szczerba będzie na innej pozycji, niż druga.
AB{x cyfr} / AB{x-1 cyfr} = nie ma takiej siły, żeby to nie była dziesiątka.
Co nam daje zero na końcu, a nawet i dwa zera.
Brawo!
mp
Liczb 1-szczerbatych zakończonych dokładnie jednym zerem jest skończenie wiele.
Dowód podam w wolnej chwili (mam nadzieje, ze przed kolejnym wpisem na blogu)
180625 / 10625 = 17
Mam niewiele czasu, dlatego umieszczam tylko zarys swoich notatek w temacie (uzupełnię, wyjaśnię innym razem):
zapis [xyz] – oznacza liczbę zlepioną z liczb x, y i z (w zależności od kontekstu z ewentualnymi zerami wiodącymi).
[AXB] – liczba 1-szczerbata niepodzielna przez 10
Zakładamy, że X to usuwana cyfra, a liczba B ma b cyfr.
[AXB] = (K+1) [AB]
P = 10^b
[AXB] = 10PA + PX + B
[AB] = PA + B
[AXB] = (K+1) * [AB]
[AXB] – [AB] = K * [AB]
[AXB] – [AB] = 9PA + PX = P * (9A + X)
P * (9A + X) = K * (PA + B)
P * ((9-K)A + X) = K * B
Lewa strona jest podzielna przez P, tzn. przez 2^b oraz 5^b. Lewa strona to iloczny liczby K (dość łatwo pokazać, że K nie przekracza 20) oraz liczby B (mniejsza od P).
Ponadto, skoro B nie dzieli się przez 10, to jeden z czynników 2^b lub 5^b musi być zawarty w K (mocno ograniczonym). To daje nam, że dla K = 16 = 2^4 możemy otrzymać, że liczba B jest 4 cyfrowa i jest to największa możliwa liczba cyfr liczby B (uwzględniając zera wiodące)
W zależności:
P * ((9-K)A + X) = K * B
Mamy tak:
P = 10 lub 100 lub 1000 lub 10000 – 4 możliwe wartości
K – ograniczone przez 20
X – 9 możliwych wartości, bo to cyfra
B – ograniczone przez P – czyli maks 10000 wartości.
A wyliczamy podstawiając konkretne wartości za parametry powyżej – w wielu przypadkach wyjdzie liczba niecałkowita, ale to nie zmienia faktu, że mamy tylko skończenie wiele kandydatów na liczbę [AXB].
To był szkic dowodu, że liczb 1-szczerbatych niepodzielnych przez 10 jest skończenie wiele.
Jak udowodnić, że liczb 1-szczerbatych podzielnych przez 10, ale niepodzielnych przez 100 jest skończenie wiele?
Takie liczby mogą być jednej z dwóch postaci:
[AXB0] = (K+1) * [AB0]
[AX0] = (K+1) * [A0]
Ten pierwszy rodzaj, to po prostu dziesięciokrotność liczb 1-szczerbatych niepodzielnych przez 10 (tych jest skończona liczba – szkic dowodu w poprzednim komentarzu – oraz podane jako fakt przez autora bloga)
Drugich jest również skończenie wiele:
[AX0] = (K+1) * [A0]
[AX0] – [A0] = K * [A0]
90A + 10X = 10KA
9A + X = KA
X – 9 możliwości
K – maks 20 możliwości
więc na A również mamy skończenie wiele możliwości
to kończy szkic dowodu, że liczba 1-szczerbatych zakończonych dokładnie jednym zerem jest skończenie wiele.
Analizując szkic dowodu na tylko skończoną liczbę liczb 1-szczerbatych niepodzielnych przez 10 można domyślić się, jak szukać największych takich liczb.
Wystarczy przyjąć, że końcówka jest 4 cyfrowa (bo to maks). Wtedy B musi dzielić się przez 5^4 = 625, K musi dzielić się przez 2^4 = 16, czyli K = 16
Zatem [AXB] / [AB] = 17
Dość szybko ręcznie można znaleźć przykłady:
180625 / 17 = 10625
191250 / 17 = 11250
Nie szukałem dokładnie, ale strzelę, że to są największe dwa przykłady liczb 1-szczerbatych niezakończonych zerem.
Prawdopodobnie chodzi o 180625.
Ciekawe jaka jest max liczba dwuszczerbata bez zera na koncu …. ?
Ciekawa jestem, ile cyfr ma mieć ta największa szczerbatka 🙂 Zdradzi Pan to?
@drugi dowód miodzia
Pozwolę sobie dodać, że z równania 9A+X=KA i faktu, że mamy skończoną liczbę możliwości na X oraz K jeszcze nie wynika, że mamy skończoną liczbę rozwiązań (na A). I dobrze, bo byśmy udowodnili coś nieprawdziwego 🙂
Wynika za to, że mamy skończoną liczbę rozwiązań oraz wszystkie rozwiązania postaci X=0 K=9 oraz A-dowolne, co daje nam wyniki kończące się na …00.
A dowód jest ślicznie elementarny (proszę absolutnie nie traktować jako krytykę).
@Esteon
1. Akurat zakładałem, że X jest różne od 0, wiec przypadek nieskończonej liczby rozwiązań odpada, aczkolwiek jest to ciekawe spostrzeżenie.
2. Cały dowód wymyśliłem w głowie, ani razu nie posilkujac się papierem i ołówkiem. Tu w komentarzach zapisywalem myśli bez większej próby ułożenia ich w logiczny ciąg, nie analizowanym przypadków szczególnych… Chciałem po prostu zapisać to, co wymyśliłem, aby nie zapomnieć. Choć teraz, po przeczytaniu własnych wpisów musze przyznać, że całkiem składnie mi to wyszło.
3. Lubię krytykę, bo dzięki niej uczę się i poznaje własne słabości. Akurat w tym konkretnym przypadku zdaje sobie sprawę, że moje notatki mogą zawierać wiele uchybień/błędów – dlatego na wstępie zaznaczyłem, że to tylko szkic. Ale chyba odpuszczę sobie dokładny opis…