Problem 196

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

Problem 196 obravnava naravna števila, ki nikoli ne postanejo palindromna števila s pomočjo iteracije dodajanja njihovih obrnjenih števk. Za takšna števila je Wade VanLandingham skoval ime števila Lychrelove, oziroma Lychrelova števila, kjer je »Lychrel« groba premetanka imena njegovega dekleta Cheryl.

Postopek:

  1. vzamemo število (npr. 5280),
  2. mu obrnemo števke (0825), pri tem vodečo ali vodeče ničle izpustimo,
  3. seštejemo obe števili 5280 + 825 = 6105,
  4. če je dobljeno število palindromno, postopek končamo, sicer pa ponovimo postopek s tem številom (6105).

Za število 5280 dobimo zaporedje: 5280, 6105, 11121, 23232. Za večino števil se ta postopek kmalu konča.

Števila v desetiškem sestavu[uredi | uredi kodo]

Vsa eno in dvomestna števila postanejo palindromna. Približno 80 % vseh števil pod 10.000 se prelevi v palindromna v 4 ali manj korakih. Okoli 90 % pa v 7 ali manj korakih.

  • Število 55 je že samo palindromno,
  • 1 postane palindromno po eni iteraciji: 1 + 1 = 2,
  • 5 postane palindromno po dveh iteracijah: 5 + 5 = 10, 10 + 1 = 11,
  • 59 postane palindromno po treh iteracijah: 59 + 95 = 154, 154 + 451 = 605, 605 + 506 = 1111,
  • 69 postane palindromno po štirih iteracijah: 69 + 96 = 165, 165 + 561 = 726, 726 + 627 = 1353, 1353 + 3531 = 4884,
  • 166 postane palindromno po petih iteracijah: 166 + 661 = 827, 827 + 728 = 1555, 1555 + 5551 = 7106, 7106 + 6017 = 13123,
  • 79 postane palindromno po šestih iteracijah:
79 + 97 = 176, 176 + 671 = 847, 847 + 748 = 1595, 1595 + 5951 = 7546, 7546 + 6457 = 14003, 14003 + 30041 = 44044,
  • 89 potrebuje kar 24 iteracij, da postane palindromno: 8813200023188,
  • 10.911 potrebuje 55 iteracij, da postane palindromno: 4668731596684224866951378664 ,
  • 9.008.299 potrebuje 96 iteracij , da postane palindromno: 555458774083726674580862268085476627380477854555,
  • sedemnajstmestno število 1.186.060.307.891.929.990 potrebuje 261 iteracij: 44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544. To število trenutno nosi svetovni rekord. Ugotovil ga je Jason Doucette 30. novembra 2005.

Prvo znano možno število, ki nikoli ne da palindromnega števila je 196. Prva možna števila so (OEIS A023108):

196, 295, 394, 493, 592, 689, 691, 788, 790, 879, 887, 978, 986, 1495, 1497, 1585, 1587,1675, 1677, 1765, 1767, 1855, 1857, 1945, 1947, 1997, 2494, 2496, 2584, 2586, 2674, ...

Za število 196 so preverili že več kot 9 milijonov iteracij, ki so dale nepalindromno število s skoraj 4 milijoni števkami. Tabela kaže število možnih števil, ki nikoli ne dajo palindromnega števila, znotraj naraščajočih območij:

Območje Možnih števil
101 0
102 0
103 2
104 69
105 99
106 1728
107 29.813

Niti, semena in sorodna števila[uredi | uredi kodo]

Nit je zaporedje števil, ki na ta način lahko ali pa ne vodijo do palindromnega števila. Vsako dano seme in pripadajoče sorodno število bo konvergiralo po isti niti. Nit ne vsebuje izvirnega semena ali sorodnega števila, ampak le števila, ki so skupna obema, potem, ko konvergirajo.

Semena tvorijo podmnožico števil, ki ne dajo palindromnega števila, oziroma najmanjšega števila, ki tvorijo nit. Nit je lahko samo palindromno število. Prvi trije primeri so prikazani krepko v zgornjem seznamu.

Sorodna števila tvorijo podmnožico števil, ki ne dajo palindromnega števila, in vsebujejo vsa števila niti, razen semena ali drugega števila, ki bo konvergiralo po dani niti po eni iteraciji. Ta izraz je vpeljal Kodži Jamašita leta 1997.

Dokaz in dvojiški sestav[uredi | uredi kodo]

Dokaza, da zgornja števila nikoli ne dajo palindromnega števila na ta način, ne poznamo. To velja za desetiški sestav. V dvojiškem sestavu so dokazali, da takšna števila obstajajo, na primer število 10110 (desetiško 22).

   10110 + 1101 = 100011
  100011 + 110001 = 1010100
 1010100 + 10101 = 1101001
 1101001 + 1001011 = 10110100
10110100 + 101101 = 11100001
 ...

Število 1100001011 (desetiško 779) na primer potrebuje 32 iteracij, da postane palindromno 10010000001011111111010000001001.

Članek je dopolnjen s člankom iz PlanetMath.org

Zunanje povezave[uredi | uredi kodo]