Weźmy np. liczbę 108, suma jej cyfr to 9
108 dzieli się przez 9 bez reszty, otrzymujemy 12
cuma cyfr to 3, 12 dzieli się przez 3 otrzymujemy 4
4/4=1
Czyli szukamy liczb, które dzielą się przez sumę swoich cyfr, a powstały iloraz też ma tą właściwość.
Powtarzanie doprowadzi nas do jedynki.
Kto powie ile jest takich liczb? A może jest ich nieskończenie wiele? Jeżeli nie to kto znajdzie największą?
Nie chcę mi się myśleć, ale strzelam że nieskończoność ;)
A wymyśliłem na poczekaniu tyle:
1, 2, 3, 4, 5, 6, 7, 8, 9 ( ;-P ) 12, 108.
edit: chyba jednak nieskończoność. Bo wystarczy udowodnić że dla każdej liczby istnieje inna liczba która podzielona przez sumę swoich cyfr da w wyniku tą liczbę. Nie chce mi się myśleć, ale to brzmi całkiem prawdopodobnie.
1-2-18-162-2916-78732-2125764-76527504-3443737680-185961834720-10041939074880-1001392206486108480
1-3-27-243-4374-118098-11802359826
1-4-12-108-1944-52488-1417176-141598557216
1-5-45-405-7290-196830-7085880-255091680-9183300480-916759703617920
1-6-54-972-97173756
1-7-21-378-3402-61236-1102248-110152051632
1-8-72-1296-23328-839808-83912775552
1-9-81-1458-13122-354294-12754584-459165024-24794911296-2474804891365056
na szybko na razie tyle znalazlem.
cyriel napisał(a)
x*10^a, gdzie a,x naleza do calkowitych? :> Jezeli nie wykluczamy podanych przez mnie przypadkow to oczywiscie istanieje nieskonczenie wiele takich liczb :)...
Na końcu musimy uzyskać jeden
cyriel napisał(a)
...btw - proste, ale fajne :) Daj wiecej takich zagadek :)
Jeszcze nie mamy rozwiązania
liczba 1 dzieli sie przez swoja sume czyli 1 ta z kolei dzieli sie przez swoja sume czyli 1. Biorac pod uwage ten przypadek to jest tych liczb nieskonczenie wiele ...
1-1-1-1-1-.... -1-.......
Czyli odpowiedz jest - nieskonczenie wiele. Co do reszty 8 przypadkow, bez dokladniejszej analizy ciezko mi powiedziec. No ale tego pierwszego przypadku nie wykluczyles ;)
mozna to jakos tak zapisac
a0 = 1
a1 = c , gdzie 1< c < 9
a2 = a1sum(a2), gdzie sum(a2) to suma cyfr liczby a2 i (sum(a2) | a2)
a3 = a2sum(a3), gdzie sum(a3) | a3
....
an = an-1 *sum(an), sum(an)|an
i tu trzeba udowdnic czy to idzie w nieskonczonosc lub nie. Nie wiem na razie jak ta zaleznosc matematycznie wyrazic.
mag.dobrowolski napisał(a)
ciekwe czy mniejsza może dać dłuższy ciąg od większej
Może dać, na przykład:
44641044 daje ciąg długości 8 (44641044 -> 1653372 -> 61236 -> 3402 -> 378 -> 21 -> 7 -> 1)
47829690 daje ciąg długości 7 (47829690 -> 1062882 -> 39366 -> 1458 -> 81 -> 9 -> 1)
Swój program (C) zmieściłem w 100 wierszach, łącznie z arytmetyką do wielkich liczb.
Wydaj mi się, że mam wszystkie takie liczby (15095 sztuk, maksymalna to 1.084*10^1433), obliczenia zajmują około 30 sekund (PIII 1GHz).
Lecz gdy odejdę od systemu dziesiętnego, a za podstawę przyjmę np. 7, 11 albo 13 to brakuje mi cierpliwości by doczekać się na wyniki. Np. więcej niż 160 tys. dla podstawy 7. Ale w układzie piątkowym jest ich tylko 73.
Byłem ciekaw, czy ktoś wpadnie na jakiś dowcipny pomysł przyśpieszający obliczenia.
Chciałbym także zweryfikować swoje wyniki.
A liczysz w reprezentacji BCD czy o podstawie 2 i konwertujesz?
Potwierdzam, że w systemie piątkowym są 73 takie liczby...
W dziesiętnym za długo mi się liczy, ale pisałem kod na szybko i jeszcze nie optymalizowałem (ale zajmuje za to 6 linii). Zastanawiam się tylko, czy lepiej poprawić konwersję do base-10 na lepszy algorytm, czy lepiej liczyć od razu w BCD, wtedy suma cyfr jest trywialna do policzenia. I jeszcze jedno, do mnożenia używasz FFT, czy jedziesz Karatsubą? Niektóre te liczby są strasznie długie - zajmują po kilkanaście linijek w konsoli.
Czyli szukamy liczb, które dzielą się przez sumę swoich cyfr, a powstały iloraz też ma tą właściwość.
Powtarzanie doprowadzi nas do jedynki.
Drugie z pierwszego nie wynika ;]
Lepiej napisać: liczby Kornela to 1 oraz liczby, które podzielone przez sumę swoich cyfr, dają inną liczbę Kornela.
Spróbujcie rozłożyć je na czynniki pierwsze, może to coś da ;p
Jak na razie jedyne co widzę to to, że jeśli liczba jest podzielna przez 3 to suma jej cyfr też i jeśli pomnoży się ją przez jakąś liczbę to pozostanie podzielna przez 3. To samo można powiedzieć o podzielności przez 9.
Troszkę się nad tym wczoraj zastanawiałem i doszedłem do wniosku, że szukanie kolejnych liczb na podstawie podanej sprowadza się do znalezienia wektora, który jest prostopadły do pewnego określonego wektora i składa się z liczb naturalnych mniejszych od 10:
daną liczbę b, którą można zapisać w postaci ciągu cyfr b0,b1,b2,...,bn. Znalezienie liczby, która wygenerowałaby podaną liczbę b sprowadza się do znalezienia takiej liczby a (a0,a1,a2,...,am), że:
sum (ai10i) = sum(ai) * [sum(bi10</sup>i)]
sum(bi*10^i) to oczywiście liczba b, więc zapis można uprościć:
sum (ai*10^i) = sum(ai) * b
Lewą i prawą sumę można przedstawić w postaci iloczynu skalarnego wektorów:
a = [a0 a1 ... am]
d = [1 10 100 ... 10^m] (ten wektor ma być pionowy)
oraz
b = [b b b ... b] - m liczb b (ten też ma być pionowy)
Mamy równanie:
ad = ab
ad - ab = 0
a(d - b) = 0
Jest to wzór na iloczyn skalarny wektorów - wektor d - b jest z góry ustalony, pozostaje tylko znaleźć wektor a.
Przykład: jaka jest liczba 4-cyfrowa, która wygeneruje liczbę 81 (?-81-9-1) ?
mamy: a = [a0 a1 a2 a3], d = [1 10 100 1000], b = [81 81 81 81]
a(d - b) = 0
[a0 a1 a2 a3] * ([1 10 100 1000] - [81 81 81 81])T = 0 (T - transpozycja)
[a0 a1 a2 a3] * [-80 -71 19 919]T = 0
-80a0 -71a1 + 19a2 + 919a3 = 0.
Jednym z rozwiązań jest a0 = 8, a1 = 5 a2 = 4 a3 = 1 czyli liczba 1458.
Pytanie brzmi: czy dla dowolnej liczby b można znaleźć m-cyfrowy ciąg a, który będzie spełniał powyższy warunek i który będzie przedstawiał liczbę?
