Advanced

Theme and variations on the 3N+1 problem

Svensson, Nils LU (2015) In Bachelor's Theses in Mathematical Sciences MATK01 20151
Mathematics (Faculty of Sciences)
Abstract
We investigate the dynamics of the Collatz map over various domains. In particular, cycles will be studied, and conditions for their existence will be provided.
Popular Abstract (Swedish)
Till de absolut mest fascinerande problemen inom matematiken hör de som är enkla att formulera och förstå sig på men som trots detta stått emot sofistikerade attacker under en längre tid. Collatz förmodan eller ”3n+1-problemet”, vilket det kanske är mer känt som, hör till denna kategori. I snart hundra år har matematiker – bland dessa, några av vår tids främsta – utan framgång angripit det. Vad är då 3n+1-problemet?

1. Börja med ett godtyckligt positivt heltal n.
2. Om n är jämnt, dela med två. Är n udda, multiplicera med tre och addera ett.
3. Upprepa steg två tills talet ett erhålls.

Fallet då n=13 kan schematiskt illustreras på följande vis:
(13->40->20->10->5->16->8->4->2->1), där pilarna representerar ”steg två”.
... (More)
Till de absolut mest fascinerande problemen inom matematiken hör de som är enkla att formulera och förstå sig på men som trots detta stått emot sofistikerade attacker under en längre tid. Collatz förmodan eller ”3n+1-problemet”, vilket det kanske är mer känt som, hör till denna kategori. I snart hundra år har matematiker – bland dessa, några av vår tids främsta – utan framgång angripit det. Vad är då 3n+1-problemet?

1. Börja med ett godtyckligt positivt heltal n.
2. Om n är jämnt, dela med två. Är n udda, multiplicera med tre och addera ett.
3. Upprepa steg två tills talet ett erhålls.

Fallet då n=13 kan schematiskt illustreras på följande vis:
(13->40->20->10->5->16->8->4->2->1), där pilarna representerar ”steg två”.
Utmaningen består i att visa att oavsett vilket tal man startar med, kommer man genom att följa ovanstående ordination, alltid ner till talet ett. Detta har visat sig vara ett synnerligen svårlöst problem. Ett inte ovanligt förfarande i svåra fall, är att formulera analoga problem på andra domäner än sin ursprungsdomän, i förhoppningen om att kunna tillämpa eventuella nyfunna insikter på ursprungsproblemet. Detta är en metodik vi utforskar i vår artikel.

I första delen studerar vi 3n+1-problemet över ringar av kongruensklasser Z/kZ. Det betyder att man delar upp heltalen i k klasser beroende på vad resten vid division med k blir. Exempel: talet 15 räknat i Z/12Z identifieras med talet 3 eftersom 15=12*1 + 3.
Företrädesvis kommer vi att studera så kallade cykler. En cykel består av ett startvärde n, som man efter ett ändligt antal tillämpningar av steg två, kommer tillbaka till. I nuläget känner man endast till en cykel för 3n+1-problemt över de naturliga talen – den ”triviala cykeln” – som utgörs av sekvensen (1->4->2->1). När man jobbar över ringar av kongruensklasser Z/kZ, är cykler en vanligare förekomst, och vi kommer bland annat att härleda kriterier på talet k, för vilka cykler existerar.

I andra delen av artikeln studerar vi en generalisering av 3n+1-problemet: det s.k. ”qn+1-problemet”. Vi studerar en viss typ av cykler – så kallade kretsar – och visar att deras existens är nära sammankopplad med existensen av heltalslösningar till en viss sorts ekvationer. Exempel på detta ges för fallet q=9. (Less)
Please use this url to cite or link to this publication:
author
Svensson, Nils LU
supervisor
organization
course
MATK01 20151
year
type
M2 - Bachelor Degree
subject
publication/series
Bachelor's Theses in Mathematical Sciences
report number
LUNFMA-4042-2015
ISSN
1654-6229
other publication id
2015:K15
language
English
id
8054582
date added to LUP
2015-11-11 13:38:22
date last changed
2015-11-11 13:38:22
@misc{8054582,
  abstract     = {We investigate the dynamics of the Collatz map over various domains. In particular, cycles will be studied, and conditions for their existence will be provided.},
  author       = {Svensson, Nils},
  issn         = {1654-6229},
  language     = {eng},
  note         = {Student Paper},
  series       = {Bachelor's Theses in Mathematical Sciences},
  title        = {Theme and variations on the 3N+1 problem},
  year         = {2015},
}