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.
x*10^a, gdzie a,x naleza do calkowitych? :> Jezeli nie wykluczamy podanych przez mnie przypadkow to oczywiscie istanieje nieskonczenie wiele takich liczb :)
mwili - liczyles w pamieci? ;P
btw - proste, ale fajne :) Daj wiecej takich zagadek :)
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
mwili napisał(a)
...
10041939074880-1001392206486108480
...
10041939074880 / 54 =
185961834720 / 54 =
3443737680 / 45 =
76527504 / 36 =
2125764 / 27 =
78732 / 27 =
2916 / 18 =
162 / 9 =
18 / 9 =
2 / 2 =
1 OK
ale 1001392206486108480 nie dzieli się przez 63
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 ;)
Powtarzanie doprowadzi nas do jedynki.
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.
Proponuję odmianę konkursu, znaleźć "liczbę Dobrowolskiego" dla której ciąg prowadzący do jedynki jest najdłuższy (lub udowodnić, że takiej liczby nie ma).
mwili@ dobry pomysł z tym liczeniem "od końca"
bo@ ciekwe czy mniejsza może dać dłuższy ciąg od większej. O! Trzeba to sprawdzić!
Liczby te mają już swoją nieformalną nazwę, to liczby Kornela.
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)
A ja znalazłem dwie różne, które dają ciągi o tej samej długości
Niby nic, ale ich różnica ma 1432 cyfry :)
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.
Możesz coś więcej napisać o swojej metodzie?
Korzystałeś ze wzoru podanego przez mwili? (czyli od 1 mnożysz kolejno)?
Krolik napisał(a)
...(czyli od 1 mnożysz kolejno)?
Pewnie, że tak
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.
Trzeba sumować i liczyć cyfry więc zdecydowałem się na BCD, a nawet ABCDE (podstawa 10^5). Istotne bo 1 mnożenie zamiast 25.
FFT raczej nie pomoże, bo wszystkie mnożenia to WIELKA*słowo
A wielkie są, dla dziesiętnego doszedłem do 1343 cyfr.
Miało być oczywiście "1 mnożenia zamiast 5"
To że dobrą podstawą jest 10^5 mogłem określić dopiero po policzeniu do końca.
Liczba przez jaką się mnoży związana jest z długością iloczynu.
Doszedłem do 1434 cyfr, czyli podstawa < 2^32/(1434*9)
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.
Podoba mi się ta definicja.
O dziewiątce wiem, ogólnie podstawa-1. Pozwala to robić znacznie dłuższe kroki.
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ę?