Podwajanie z sortowaniem

Bierzemy jedynkę, zapisujemy ją. Mnożymy przez dwa, dostajemy dwójkę. Zapisujemy. Mnożymy przez dwa, zapisujemy czwórkę. Mnożymy przez dwa, zapisujemy ósemkę. Mnożymy przez dwa, zapisujemy 16. I teraz uwaga: mnożymy przez dwa, sortujemy cyfry, wynik zapisujemy (16*2=32, po posortowaniu = 23). 23*2=46, zapisujemy. 46*2=92, po posortowaniu 29, zapisujemy. Na chwilę obecną mamy więc:

1, 2, 4, 8, 16, 23, 46, 29, ...

Czy powyższa sekwencja się kiedykolwiek zapętli? Podwajanie zwiększa liczbę, sortowanie cyfr - zmniejsza. Hmmm...

Otóż - zapętli się: 1, 2, 4, 8, 16, 23, 46, 29, 58, 116, 223, 446, 289, 578, 1156, 1223, 2446, 2489, 4789, 5789, 11578, 12356, 12247, 24449, 48889, 77789, 155578, 111356, 122227, 244445, 48889.

A co jeżeli wystartujemy od jakiejś innej liczby? Na przykład, dajmy na to, od piątki?

Akurat piątka to kiepski przykład, bo 5*2=10 czyli po posortowaniu 1. No to może 6?

6, 12, 24, 48, 69, 138, 267, 345, 69

Hmm. 7?

7, 14, 28, 56, 112, 224, 448, 689, 1378, 2567, 1345, 269, 358, 167, 334, 668, 1336, 2267, 3445, 689

Chyba się zawsze zapętli.

A jeżeli zamiast przez dwa będziemy mnożyć przez trzy?

Trójka jest mało wdzięczna, bo zawsze błyskawicznie dojdziemy do 45, a tu już pętla: 45, 135, 45, 135, 45...

A przez pięć?

Wbrew intuicji, piątka zapętla się całkiem interesująco i w różny sposób w zależności od tego, od jakiej liczby zaczniemy:

1, 5, 25, 125, 256, 128, 46, 23, 115, 557, 2578, 1289, 4456, 2228, 1114, 557

3, 15, 57, 258, 129, 456, 228, 114, 57

7, 35, 157, 578, 289, 1445, 2257, 11258, 2569, 12458, 2269, 11345, 25567, 123578, 16789, 34589, 124579, 225689, 1124458, 222569, 1112458, 225569, 1124578, 225689

9, 45, 225, 1125, 2556, 1278, 369, 1458, 279, 1359, 5679, 23589, 114579, 255789, 1245789, 2245689, 11224458, 1222569, 1124568, 224568, 112248, 12456, 2268, 1134, 567, 2358, 1179, 5589, 24579, 122589, 124569, 224568

Kolejne mnożniki dają nam zawsze pętlę, ale nie wszystkie. Przy mnożniku = 21 poddałem się po wyznaczeniu kilkudziesięciu tysięcy wyrazów ciągu. Podobnie jest z 23 i 29. Dalej nie szukałem, zabrakło mi rozpędu.

Jakieś pomysły? Przemyślenia?

Hmmm.

9 komentarzy

  1. step = 2
    value = 1
    maxTry = 100

    def sort(val):
      arr = [] 
      arr[:0]=str(val)
      arr.sort()
      em =”
      em = em.join(arr)
      return int(em)

    def test(step):
      result = []  
      value = 1   
      loop = False
      for counter in range(1,maxTry):
        value *= step
        value = sort(value)
        if value in result:
          result.append(value) # to shop duplicate 😉
          print(‘Loop detected for step {}, value: {}, set: {}’.format(step, value, result))   
          loop = True
          break
        else:
          result.append(value)

      if not loop:
        #print(‘Loop not detected for step: {}, number of multiplications {}. Set = {}’.format(step, maxTry, result))           
        print(‘Loop NOT detected for step: {}, number of multiplications {}’.format(step, maxTry ))           
      print(‘———————-‘)  

    for x in range(2,30):
      test(x)

    1. maxlen=5000
      print("first,mul,loop,len,last,looplen")
      for mul in range(2, 99):
          for first in range(1, 99):
              n = first
              seq = []
              counter = 0
              while not n in seq:
                  seq.append(n)
                  n = int(''.join(sorted(str(n*mul))))
                  counter += 1
                  if counter > maxlen:
                      print(f"{first},{mul},no,-1,-1,-1")
                      break
      
      
              if counter <= maxlen:
                  seq.append(n)
                  print(
                      f"{first},{mul},yes,{len(seq)},{seq[-1]},{len(seq)-seq.index(seq[-1])-1}")
      
      1. W przedziale mnożników 1-99 najdłuższa sekwencja do napotkania pierwszej pętli ma 462 elementy i pojawia się dla kombinacji mnożnik=65, startując od 49. Element powtórzony to 11234455667778800

        Najdłuższy powtórzony element pojawia się dla mnożnika 98, startując od 47, i wynosi 1122277788888888888888888888888888888888888888888888899 (po 103 krokach)

        Najdłuższa pętla (czyli ilość elementów od pierwszego do drugiego wystąpienia powtórzonego elementu) to 24, pojawia się kilkukrotnie dla mnożnika 11.

  2. Trafiło mi się zadanie dla programistów (i/lub matematyków). Podobnie, jak poprzednie, z zaskakującym rozwiązaniem – innych chyba nie znam.. Nie wiem, czy mogę ci się wcinać na twój blog? Własnego nie mam, gdyż za mało zadań wymyślam lub przetwarzam, aby prowadzić tak ważne przedsięwzięcie. Ot, jedno, dwa w roku… Zaryzykuję, że mnie nie zbanujesz.

    Zadanie: Należy znaleźć jak największą liczbę naturalną K, która jest kwadratem iloczynu swoich cyfr.

    Widzę, choćby po wpisach do tej notki, że potraficie liczyć na bardzo dużych liczbach (u Gospodarza było 55 cyfr). To dobrze, ta umiejętność przyda się 🙂 Zadanie jest świeżutkie. Na pogromcę K czeka niebo pełne dziewic.
    Powodzenia!

    1. Nie zbanuję. Masz dobry timing, bo dosłownie 20 minut temu córka pytała ile osób czyta (i komentuje) Ignormatyka i jej powiedziałem, że komentujących jest nieduża garstka raptem kilkunastu osób, i pokazałem jej najczęstszych gości, w tym również ciebie. Wystąpiłeś jako “taki mądry facet od zagadek”. Tak że możesz sobie walnąć odznakę w wolnej chwili 😉 A zagadka dobra, rzucę na nią okiem, ale raczej już nie dziś.

    2. Jedynka?

      Potem aż do miliarda nie ma takiego K. Dalej jeszcze nie sprawdzałem. Do 55 cyfr póki co daleko…

      Ponadto:

      (1) K nie może zawierać zera
      (2) Jeżeli K zawiera piątkę, musi kończyć się piątką (i zawierać wyłącznie cyfry nieparzyste)
      (3) Średnia geometryczna cyfr K nie może być większa od ~3.16 (pierwiastek z 10), inaczej kwadrat iloczynu cyfr K będzie miał więcej cyfr od K.

      Czym większe liczby, tym rzadziej znajdujemy kwadraty spełniające (2) – przy czym udało mi się znaleźć mnóstwo przykładów bez piątki (16 313 321 188 ^ 2 = 266 124 448 182 849 731 344; 16 313 321 232 ^ 2 = 266 124 449 618 421 997 824 i tak dalej), ale ani jednego z piątką.

      Co do (3) to nie jestem pewien, intuicja mówi mi, że to poprawny warunek. Jeżeli tak jest, to bardzo mocno ogranicza on nasze możliwości…

      Hmmm.

      1. (1) jest ok
        (2) K nie może zawierać 5, gdyż jest kwadratem, a każdy kwadrat>9 zawiera cyfrę parzystą. Cyfra parzysta * 5 daje na końcu 0.
        (3) ok, ale na oko chyba mało praktyczne w zastosowaniu.

        Podpowiedź: jak się dobrać do K ciut głębiej, to wychodzi, że jej dzielnikami mogą być tylko 2, 3 i 7. Takich liczb, im są większe, jest coraz mniej, a jak jeszcze większe, to jeszcze bardziej mniej, więc daleko od zera liczy się szybko. Dzięki temu wyniki aż do 10^100 są mi znane. Chodzi o te większe liczby. 🙂

        W tym zadaniu kryje się Wielka Tajemnica. Nie wiem ile osób je przeczytało i próbuje swoich sił, więc jeszcze chwilę poczekam z wyjaśnieniem.

      2. Obiecałem Tajemnicę i oto ona: to zadanie jest, jak się wydaje, zupełnie świeżą hipotezą mówiącą, że nie istnieje opisywana wcześniej liczba K>1. Jak wiadomo hipotezy albo poprzez dowód zamienia się w twierdzenia, albo poprzez inny dowód obala, albo… znajduje się kontrprzykład, który od razu bez skrupułów wysyła hipotezę do kosza. Kontrprzykładem byłoby to znalezienie tej liczby.
        Wrzuciłem to zadanie będąc zafascynowany tym, z jaką łatwością wykonujesz obliczenia na bardzo dużych liczbach. Liczyłem, że mając taaakie języki i taaakie biblioteki matematyczne będzie możliwe uzyskanie wyniku większego niż 10^100.
        Zawiedziony nie jestem, gdyż wiem, jakie to jest trudne. Obecnie piszę sam takie funkcje starając się je zoptymalizować do tego konkretnego problemu, aby były wydajniejsze od uniwersalnych gotowców. Liczę na wyniki rzędu 10^120.

        Odnośnie hipotezy. Na pierwszy i na kolejne rzuty oka nie widać żadnych matematycznych przeszkód, aby K istniało! Tymczasem kwadraty iloczynów jej cyfr w magiczny sposób omijają wartość K. Być może jest to kolejna, po liczbach pierwszych, ciągu Collatza, itp. nierozwiązywalna “zagadka” (czytaj: Wielki Problem Matematyczny). Kto wie?

Leave a Comment

Twój adres e-mail nie zostanie opublikowany.