Czynniki N
Każdą liczbę złożoną da się rozłożyć na czynniki pierwsze – przynajmniej dwa. Wśród nich można wskazać czynnik N – taki, że większego od niego nie ma. N może być jednym z kilku równych czynników, jak 3 w rozkładzie 27 lub 36, albo największym – jak 7 w rozkładzie 35.
Zadanie brzmi tak: z dziesięciu różnych cyfr należy utworzyć n takich liczb złożonych, aby suma ich czynników N była największa.
Nie ulega wątpliwości, że w ogólnym przypadku suma N będzie największa dla najmniejszego n=1, czyli praktycznie dodawania nie będzie. Należałoby po prostu znaleźć 10-różnocyfrową liczbę z największym N. Suma cyfr takiej liczby podzielna jest przez 9, więc sama liczba też, czyli najlepiej, aby miała postać 3^2*N. Liczbą tą jest 9876541023=3^2*1097393447. Znaleźć ją łatwo, mnożąc przez 9 kolejne coraz mniejsze liczby pierwsze, zaczynając od największej mniejszej od 9876543210/9. Pisanie programu jest zbędne, wystarczy kalkulator, bo bardzo szybko wyskakuje właściwy wynik, czyli liczba złożona z różnych cyfr.
Największe n równe jest oczywiście 7 – cztery 1-cyfrowe i trzy 2-cyfrowe liczby złożone. Jaka jest w tym przypadku największa suma N? A kto znajdzie największą sumę N dla n=6 (nie znam rozwiązania)?
Komentarze
Ręcznie znalazłem 3784 i na razie wydaje mi się, że lepiej być nie może, ale jest późno, więc wszystko jest możliwe 😉
No tak, lepiej się nie da ale to jest złe rozwiązanie. „Ogarnąłem” wszystkie warunki zadania chyba bez komputera się nie obejdzie 🙁
Jeżeli dobrze zrozumiałem, to N=4+6+8+9+88+9999=10114
4*6*8*9*88*9999=1520487936
Oj, nie o to chodzi. Zapewne to efekt mojego zbyt pokrętnego pisania.
mp
Obliczone na komputerze największe sumy dla n=2..7 (w nawiasie największy dzielnik pierwszy, czyli N):
n=2: suma=493761555 liczby: 987523106(493761553) 4(2)
n=3: suma=49185756 liczby: 98371502(49185751) 4(2) 6(3)
n=4: suma=4376559 liczby: 8753102(4376551) 4(2) 6(3) 9(3)
n=5: suma=83699 liczby: 753201(83689) 4(2) 6(3) 8(2) 9(3)
n=6: suma=2432 liczby: 30(5) 7251(2417) 4(2) 6(3) 8(2) 9(3)
n=7: suma=41 liczby: 30(5) 21(7) 4(2) 57(19) 6(3) 8(2) 9(3)
dla n=6 to np. pierwsze z rzędu liczby 10, 23, 45, 67, 8, 9 tak? Dobrze zrozumiałem definicję?
Tak, ale nie do końca, bo liczby powinny być złożone, a 23 i 67 są pierwsze.
mp
Dzień dobry. Pierwsza część zadania: 4, 6, 8, 9, 21, 30, 57, co daje sumę 2+3+2+3+7+5+19 = 41. Cdn.
4=2*2 (2)
6=2*3 (3)
8=2*2*2 (2)
9=3*3 (3)
57=3*19 (19)
30=2*3*5 (5)
21=3*7 (7)
N=41
4=2*2
6=2*3
8=2*2*2
9=3*3
30=2*3*5
7251=3*2417
N=2+3+2+3+5+2417=2432
Cd – przypadek „6”. To jest bardzo fajne zadanie, rozwiązywanie przypomina nieco opowieść kryminalną z licznymi zwrotami akcji jeśli chodzi o podejrzanych. Najpierw krąg należy zawęzić poprzez zauważenie, że wśród liczb ułożonych z 10 różnych cyfr powinna być jedna jak najdłuższa, w tym konkretnym przypadku liczba 4-cyfrowa, która wraz z czterema jednocyfrowymi znanymi z poprzedniej części oraz jedną dwucyfrową lepiej rokuje, niż na przykład cztery jednocyfrowe i dwie trzycyfrowe, nie mówiąc o dwóch jednocyfrowych i czterech dwucyfrowych. Należy więc sprawdzać liczby 4-cyfrowe poczynając od 7532 i dalej coraz mniejsze. Już (albo dopiero) przy 7352 okazuje się, że intuicja, nakazująca poszukiwanie liczby 4-cyfrowej, była słuszna. Kolejnym pewniakiem wydawała się 7302, ale ostatecznie stanęło na 7251. Tropy próbowała jeszcze zmylić 5702, no ale przecież ani 13, ani 31 nie są liczbami złożonymi. Dlatego mamy, od największej, 7251, 30, 9, 8, 6, 4, i dodawanie 2417+5+3+2+3+2=2432. Dziękuję i pozdrawiam 🙂
n=6
sześć szukanych liczb to:4,6,8,9,30,7251
ich czynniki N to:2,3,2,3,5,2417
suma czynników N=2432
n = 6
liczby: 7251, 30, 4, 6, 8, 9
czynniki N: 2417, 5, 2, 3, 2, 3
rozwiązanie: 2417+15= 2432
Uwagi: problem arcyciekawy. Większości dużych 4-cyfrowych kandydatów towarzyszy dwucyfrowa liczba pierwsza.
Założyłem, że 0 nie może być 1. cyfrą żadnej liczby.
n=7
sześć szukanych liczb to:4,6,8,9,21,30,57
ich czynniki N to:2,3,2,3,7,5,19
suma czynników N=41
32, 51, 70 oraz jednocyfrowe 4,6,8,9 dają sumę N = 65
Dla n=6 zakładam, że rozwiązanie powinno być wśród układów: 4-cyfrowa, 2-cyfrowa i wszystkie 1-cyfrowe – pod warunkiem, że znajdziemy 4-cyfrową liczbę, której rozkład da nam szybko jakąś wysoką liczbę pierwszą – sprawdziłem układy: dwie 3-cyfrowe, cztery 1-cyfrowe i moim kandydatem tutaj jest 753, 201, 4,6,8,9, wtedy N = 292. Jak znajdę kolejną wolną chwilę poszukam dalej – sęk w tym ,że uparłem się, żeby zadania wykonywać bez wykorzystania googla, wiki, kalkulatora, excela, c – i o ile 3-cyfrowe liczby pierwsze łatwo odsiewam, to dla 4-cyfrowych potrzeba dłuższej chwili, a ten tydzień jakoś nie sprzyja, bo trzeba poniańczyć czworonoga a nie czterocyfrowce.
Szukam ręcznie, póki co największą sumę największych dzielników jaką znalazłem dają liczby: 4, 6, 9, 21, 30, 758. Szukana suma: 399
Jest jednak lepsze rozwiązanie.
4, 6, 8, 9, 30, 7251
Suma najwyższych dzielników pierwszych to 2432.
Troszkę się nakombinowałem z programem, oto wyniki:
n: 1 Suma N: 1097393447 liczba: [9876541023]
n: 2 Suma N: 493761555 liczby: [4, 987523106]
n: 3 Suma N: 49185756 liczby: [4, 6, 98371502]
n: 4 Suma N: 4376559 liczby: [4, 6, 9, 8753102]
n: 5 Suma N: 83699 liczby: [4, 6, 8, 9, 753201]
n: 6 Suma N: 2432 liczby: [4, 6, 8, 9, 30, 7251]
n: 7 Suma N: 41 liczby: [4, 6, 8, 9, 21, 30, 57]
Pozdrawiam
PS. Ciekawe do czego może się przydać taka suma?
Gdyby taka suma była wyznaczana jednoznacznie to mogłaby posłużyć do stworzenia całkiem przyzwoitego ale w miarę prostego algorytmu szyfrującego
jak widzę zapędziłem się – i rozwiązałem inne zadanie – sumowałem WSZYSTKIE czynniki rozkładu poszczególnych liczb na czynniki pierwsze zamiast największych