{"id":2330,"date":"2010-09-17T02:30:55","date_gmt":"2010-09-17T00:30:55","guid":{"rendered":"https:\/\/xmau.com\/wp\/ilpost\/?p=2330"},"modified":"2022-10-10T19:00:49","modified_gmt":"2022-10-10T17:00:49","slug":"il-problema-3n1","status":"publish","type":"post","link":"https:\/\/xmau.com\/ilpost\/2010\/09\/17\/il-problema-3n1\/","title":{"rendered":"Il problema 3n+1"},"content":{"rendered":"

Prendete il vostro linguaggio di programmazione favorito, o anche solo carta e penna, e iniziate a fare le seguenti operazioni (se siete tipi informatici, “implementate il seguente algoritmo”). Partite da un numero intero qualsiasi: se \u00e8 dispari lo moltiplicate per 3 e poi aggiungete uno al risultato, ottenendo un numero pari; se \u00e8 pari lo dimezzate, ottenendo… non si sa se un numero pari o dispari. Ripetete la cosa finch\u00e9 non ottenete un numero gi\u00e0 visto (e quindi entrate in un ciclo infinito), oppure ottenete valori sempre pi\u00f9 grandi, e quindi finite nello spazio numerico profondo. Cosa succeder\u00e0?<\/p>\n

Partendo da 1, otterremo 4, 2, 1; abbiamo trovato un ciclo di lunghezza 3. Con 2 ovviamente capita la stessa cosa; prendendo 3, avremo 10, 5, 16, 8, 4, 2, 1 e siamo di nuovo sul ciclo iniziale. Con 7, l’ottovolante dei numeri d\u00e0 22, 11, 34, 17, 52, 26, 13, 40, 20, 10… Toh, un numero gi\u00e0 visto: anche stavolta insomma arriviamo al ciclo 1-2-4-1. Sar\u00e0 sempre cosi? Non si sa. Il problema \u00e8 noto come Congettura di Collatz<\/a>, dal nome di chi propose nel 1937; ma \u00e8 anche nota come “3n+1” (dall’operazione da fare quando si ha un numero dispari), o con tanti altri nomi diversi, il che mostra che ci hanno pensato su in tanti. D’altra parte, se Erd\u0151s afferm\u00f2 che “la matematica non \u00e8 ancora pronta per problemi di questo tipo” e offr\u00ec ben 500$ a colei o colui che fosse riuscito a risolverlo vorr\u00e0 ben dire qualcosa.<\/p>\n

\"\"<\/a>
orbite dei numeri da 1 a 20 nella congettura 3n+1<\/figcaption><\/figure>A dire il vero ci sono numeri di partenza che danno delle false speranze, mettendoci un bel po’ prima di stabizzarsi su quel ciclo; se volete divertirvi, provate a vedere cosa succede partendo da 27. Meglio usarla davvero, la calcolatrice: prima di arrivare a 1 ci sono 111 passi, e si arriva fino a 9232! Ma il destino sembra ineluttabile: come racconta Mathworld<\/a>, la congettura \u00e8 stata dimostrata per numeri fino a circa 5,48·1018<\/sup> (no, non li hanno provati tutti, ci sono tecniche raffinate che permettono di saltare molti valori), e se c’\u00e8 un ciclo diverso da quello banale esso deve contenere almeno 275000 valori; e a quanto ne so praticamente tutti i matematici, pur sapendo bene che l’evidenza numerica non serve a nulla, la ritengono vera. <\/p>\n

Il bello \u00e8 che basta cambiare di poco le condizioni iniziali per ottenere risultati diversi. Prendiamo ad esempio la non-congettura “3n-1”. Partendo da 1 otteniamo un ciclo 1-2, e partendo da 3 si passa da 8, 4, 2 prima di finire di nuovo nel ciclo; per\u00f2 se prendiamo come numero di partenza 5 il nostro viaggio passa per 14, 7, 20, 10, 5, e in questo caso abbiamo pertanto almeno due cicli possibili. Con la non-congettura “5n+1” la situazione \u00e8 ancora peggiore; partendo da 7, infatti, il programmino che ho scritto in fretta e furia ha rapidamente superato il limite massimo dei numeri interi rappresentabili dal mio computer, e quindi immagino che i valori corrispondenti crescano senza limite. La cosa mi torna anche statisticamente; quando si arriva a un numero dispari il passo successivo ci porta a un numero pari dell’ordine di cinque volte quello iniziale; in met\u00e0 dei casi il numero non \u00e8 divisibile per 4 e quindi anche il secondo passo ci lascia un numero superiore a quello di partenza. Ammetto di non aver voglia di dimostrarlo formalmente, per\u00f2… <\/p>\n

Andando ancora pi\u00f9 vicini a una soluzione, la non-congettura “3n+5” ha un ciclo che parte con 38, un numero non esattamente immaginabile a prima vista; e la stessa “3n+1”, se la estendiamo ai numeri negativi, ci d\u00e0 tre ulteriori cicli che iniziano con -1, -5 e -17, oltre all’ovvio ciclo-pappagallo che ripete ad libitum “zero, zero, zero…”. Tutto questo pu\u00f2 fare pensare che la mancanza di altri cicli sia proprio un caso, e probabilmente \u00e8 proprio cos\u00ec: come molti problemi della teoria dei numeri, si pensi alla Congettura di Goldbach, non c’\u00e8 una via maestra per risolverli proprio perch\u00e9 sono degli accidenti della storia dei numeri. Ci\u00f2 non toglie che ci sia un’estesissima bibliografia al riguardo: se volete incominciare ad avere un’idea anche grafica di cosa si sa, date un’occhiata la pagina della successione delle lunghezze<\/a> nell’On-Line Encyclopedia of Integer Sequences. <\/p>\n","protected":false},"excerpt":{"rendered":"

La congettura di Collatz \u00e8 semplicissima da enunciare, ma ancora oggi non si sa se \u00e8 vera o falsa, nonostante tutti gli studiosi che vi si sono cimentati.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":4,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[1],"tags":[],"class_list":["post-2330","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/phh2yP-BA","jetpack-related-posts":[{"id":1503,"url":"https:\/\/xmau.com\/ilpost\/2019\/07\/10\/numeri-felici\/","url_meta":{"origin":2330,"position":0},"title":"Numeri felici","author":".mau.","date":"10\/07\/2019","format":false,"excerpt":"una categoria di numeri con propriet\u00e0 facili da studiare... ma non troppo.","rel":"","context":"In \"didattica della matematica\"","block_context":{"text":"didattica della matematica","link":"https:\/\/xmau.com\/ilpost\/tag\/didattica-della-matematica\/"},"img":{"alt_text":"","src":"https:\/\/i0.wp.com\/xmau.com\/wp\/ilpost\/wp-content\/uploads\/sites\/4\/2019\/07\/happynumbers.png?resize=350%2C200","width":350,"height":200},"classes":[]},{"id":2422,"url":"https:\/\/xmau.com\/ilpost\/2011\/07\/12\/6174-196-e-altri-numeri\/","url_meta":{"origin":2330,"position":1},"title":"6174, 196 e altri numeri","author":".mau.","date":"12\/07\/2011","format":false,"excerpt":"Alcuni numeri sono pi\u00f9 interessanti di altri, almeno per chi ama cercare le loro propriet\u00e0 strane.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2598,"url":"https:\/\/xmau.com\/ilpost\/2013\/04\/26\/parilandia\/","url_meta":{"origin":2330,"position":2},"title":"Parilandia","author":".mau.","date":"26\/04\/2013","format":false,"excerpt":"Noi diamo per scontata la fattorizzazione unica, ma non \u00e8 sempre cos\u00ec.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2662,"url":"https:\/\/xmau.com\/ilpost\/2015\/12\/31\/risposte-ai-problemini-per-natale-2015\/","url_meta":{"origin":2330,"position":3},"title":"Risposte ai problemini per Natale 2015","author":".mau.","date":"31\/12\/2015","format":false,"excerpt":"Ricordate i problemi di venerd\u00ec scorso? Eccovi le soluzioni! (avevate visto, vero, che passando col mouse tenendo schiacciato il pulsante appariva l'aiutino?) 1. Fibonacci Per un qualunque intero m, i valori della successione di Fibonacci modulo m prima o poi si devono ripetere: banalmente, ci sono solo m2 possibili coppie\u2026","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2608,"url":"https:\/\/xmau.com\/ilpost\/2013\/05\/14\/no-ne-bastano-tre-pillole\/","url_meta":{"origin":2330,"position":4},"title":"no, ne bastano tre [Pillole]","author":".mau.","date":"14\/05\/2013","format":false,"excerpt":"un altro passo verso la soluzione della congettura di Goldbach","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":194,"url":"https:\/\/xmau.com\/ilpost\/2011\/09\/05\/gira-la-carta\/","url_meta":{"origin":2330,"position":5},"title":"Gira la carta","author":".mau.","date":"05\/09\/2011","format":false,"excerpt":"Una specie di gioco di prestigio matematico: l'asso galleggia sempre e si porta all'inizio del mazzetto di carte...","rel":"","context":"In \"combinatoria\"","block_context":{"text":"combinatoria","link":"https:\/\/xmau.com\/ilpost\/tag\/combinatoria\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2330","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/comments?post=2330"}],"version-history":[{"count":1,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2330\/revisions"}],"predecessor-version":[{"id":2331,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2330\/revisions\/2331"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/media?parent=2330"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/categories?post=2330"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/tags?post=2330"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}