Alegem orice numar natural "n".
Daca "n" este par aplicam relatia "n/2"
Daca "n" este impar aplicam relatia "3*n+1".

Interesant ca daca aplicam acest algoritm de calcul majoritatea numerelor naturale par sa atinga in final valoarea 1.

Spre exemplu:
n=5
3*5+1=16
16/2=8
8/2=4
4/2=1

Oare de ce?
Se poate demonstra matematic ca acest lucru este valabil pentru toate numerele naturale?
Sau exista numere care nu respecta regula?

Îl iau pe 7.
3*7 + 1 = 22
22/2 = 11
Mai departe ce fac?

11 este impar, deci:

3*11+1=34
34 este par, deci:

34/2=17

17 este impar:

3*17+1=52
52/2=26
26/2=13
3*13+1=40
40/2=20
20/2=10
10/2=5
3*5+1=16
16/2=8
8/2=4
4/2=1

M-am chinuit să scriu o demonstrație „clasică", dar pare destul de complicat. Prima oară, însă, m-am gândit la varianta mai simplă de a transforma un număr impar în număr par: Dacă n e impar, n+1 par (aplicând n+1 în loc de 3n+1 se ajunge în mod cert la 1).

Fie un număr x. Făcând împărțiri repetate la 2 până la urmă vom ajunge în mod cert la un număr impar de la x. Deci este de înțeles să presupun că n este impar (numărul obținut dintr-un x). Astfel aplic relația 3n+1. M-am gândit eu la acel n+1 și am ajuns la 2n+n+1. De aici am încercat să fac o demonstrație „clasică" care nu a mers bine. Am schimbat perspectiva și am construit o structură arborescentă, presupunând că există o continuă alternanță de la impar la par (până într-un punct).
Astfel fiul stâng al rădăcinii este 2n/2, iar fiul drept (n+1)/2. Fiul stâng practic va imita cu întârziere fiul drept. Deci pun accentul pe fiul drept care va avansa la (n+1)/2^(k+1) cât timp (n+1)/2^k e par. Dacă nu e par, (n+1)/2^k va deveni un alt n, să zicem n prim. Structura arborescentă va fi aceeași. Practic la pasul k se obține n prim+(n+1)/2^k+(n+1)/2^(k-1)+... De aici îmi vine în minte o serie pe care ai prezentat-o în altă întrebare și care are ca rezultat 1 (se adună frunzele arborelui - care nu se observă prea bine din ce am desenat eu). La un moment dat algoritmul se va opri și se va face respectiva sumă 1. Nu îți pot da o demonstrație riguroasă și completă, că și așa am stat destul pe asta și nu am atâta timp. Dar am zis să împărtășesc această viziune. Sunt curios ce idei mai vin și dacă e o perspectivă care poate duce undeva.

https://ibb.co/RyStSyH

Sa spunem ca x=6.
Pasul 1: 6 este par, deci voi obtine 6/2=3
Pasul 2: 3 este impar, deci obtin 3*3+1=10
Pasul 3: 10 este par, 10/2=5
Pasul 4: 5 este impar, deci 3*5+1=16
Pasul 5: 16 este par, obtinem 8
Pasul 6; 7 si 8: se obtine 4; 2 si in final 1.

Asta este logica corecta a problemei.


In rationamentul tau tu aplici urmatoarea logica:

Sa spunem ca x=6.
Pasul 1: 6 este par, deci voi obtine 6/2=3
Pasul 2: 3 este impar, deci obtin 3*3+1=10
Pasul 3: Pe 10 il scriem ca doua numere distincte: 3 si respectiv 2.

Deja nu mai are legatura.
Algoritmul pe care il aplici tu nu este echivalent cu algoritmul problemei.

https://ibb.co/pKRnp4N

Da, trebuia să îmi iau și un exemplu să mă verific. Suma trebuie făcută la fiecare pas (pe fiecare nivel: ex. 3 trebuia adunat cu 2 pentru a obține 5) și algoritmul reluat. Am refăcut generalizarea pe aceeași idee (sper că nu am greșit ceva din nou).

https://ibb.co/FYnrd0z

Se pare că pentru a obține n par se aplică formula:
n+(n+1)/2+(3n+3)/2^2+((3^2)n+3^2)/2^3+((3^3)n+3^3)/2^4+...=
= n+ Sumă ((n*3^(k-1)+3^(k-1))/2^k), k fiind pasul (format de fapt din 2 pași în exemplul tău - alternanța impar-par e un pas) când se obține număr par după împărțirea la 2.
Ideea cred că e să se demonstreze că se fac îndeajuns de multe împărțiri succesive la 2. Altfel spus suma fiecărui k obținut înmulțit cu 2 să fie mai mică decât numărul total de pași.
Totuși nu știu cât ar ajuta forma generală și nu știu cum aș putea dezvolta mai mult.

Https://en.wikipedia.org/wiki/Collatz_conjecture

Interesant. E un bun exercițiu de implementat prin program pentru a exersa arborii și chiar o bună aplicare a tehnicii de memoizare.
Practic ipoteza că mereu se ajunge la 1 ar fi demonstrată ca fiind falsă dacă s-ar obține un graf (graful tuturor numerelor naturale) care nu e conex. Astfel o porțiune conexă care nu este complementară grafului ce include nodul 1 ar trebui să se ducă cu nodurile spre infinit sau să aibă un ciclu către un nod din porțiune. Eu mă gândisem strict la posibilitatea că nodurile se duc spre infinit, adică nu se realizează îndeajuns de multe împărțiri la 2 pentru a ajunge pe porțiunea cu 1. Chiar dacă ar exista o asemenea porțiune de graf, aceea ar conține numere imense, având în vedere că s-au făcut simulări pentru numere foarte mari.
Oricum, nefiind demonstrată, rămâne un simplu exercițiu de gândire sau de exersare în programare.

Uneori mă întreb: la ce ne trebuie să ştim suma termenilor unei serii, la ce ne trebuie soluţia conjecturii lui Colatz, de ce vrem neapărat să cunoaştem originea cuvântului "evreu" şi multe altele ca acestea. Dar, aşa e firea omului, curios să ştie totul despre tot.

Https://www.tpu.ro/......-obtinand/

Am si uitat ca o conversatie similara a avut loc in 2017.
Imi place ca nedumerirea ta referitoare la cerinta problemei a ramas neschimbata. :))
Si atunci tot pe 7 l-ai ales ca exemplu. Parca ai fi pe "repeat". :))

Destul de interesant. Ar fi tare daca ai putea sa faci un program care să verifice primele 100000 de numere mai mari ca 1.
Asa cum ai facut in 2017. :))

https://www.tpu.ro/......-obtinand/

Ai uitat de conjectura lui Collatz? :))

Uitasem! Hai, că e amuzant. Îmi amintesc totuși de acele răspunsuri, parțial. Nu puteam să le leg de această întrebare sau să pot să mi le amintesc fără să le citesc din nou. E nostalgic.
Ai memorie bună, eu am îmbătrânit.
E clar că aveam altă perspectivă pe atunci, dar tot la programare îmi era gândul...
Dacă ar fi să fac un program acum aș implementa un arbore sau aș încerca să aplic tehnica memoizării sau aș merge pe formula pe care am dedus-o anterior. Atunci implementam algoritmii fără să implic strategii de programare sau structuri de date logice ceva mai complexe. Mergeam strict pe datele problemei. Eram și eu la facultate (una care nu mergea strict pe programare) și nu prea îmi era gândul la frumusețea implementării eficiente a algoritmilor, cât îmi era la trecerea examenelor. Aș merge și mai departe de 100000. Ar fi un challenge să fac un program în Matlab și să vedem și niște grafice, nu numai numere înșiruite. Dar acum am mai multe de făcut decât aveam pe atunci. Totuși, dacă voi exersa și un mediu vizual de programare ceva mai mult promit că mă voi gândi la această problemă (dacă nu uit).

Https://www.youtube.com/watch?v=094y1Z2wpJg&t=637s&ab_channel=Veritasium

Da, au testat imens de multe numere pe super-computere (probabil) cu un anumit timp de simulare care nu cred că a fost doar de câteva secunde. Însă exercițiul e frumos să fie rezolvat, chiar dacă a fost rezolvat mai bine de alții, așa ca hobby și ca provocare. 100000 e totuși un număr mic pentru un computer să proceseze. E mai mult pus din punct de vedere demonstrativ. Nu aș încerca să bat numărul ăla monstruos. Oricum cine știe ce strategii s-au mai folosit în acel algoritm ca să funcționeze cât mai eficient posibil? Cât despre conjunctură, pare să fie adevărată, însă e greu să se construiască o demonstrație completă matematică.
Asta mă duce cu gândul la problema Monty Hall și la câte controverse a generat până să se realizeze simularea pe calculator.
Din păcate în acest caz calculatorul nu poate realiza o demonstrație pentru toate numerele, oricât de departe ai merge. Doar să ai norocul să dai în cele din urmă peste numărul care nu respectă regula, ceea ce nu știu cât de probabil e.

Https://www.youtube.com/watch?v=094y1Z2wpJg
:))

Hai să-ţi vând un pont. Ştiai că la un patrulater inscriptibil produsul a două laturi opuse adunat cu produsul celorlalte două laturi este egal cu produsul diagonalelor? Dacă nu, cred că te bucuri acum că ai aflat ceva nou.