Een hardnekkige lusrij

Moderators: dirkwb, Xilvo

Reageer
Berichten: 433

Een hardnekkige lusrij

Het begingetal van een nieuwe rij positieve, gehele getallen is vrij te kiezen.
Als een term een priemgetal p is, dan is de volgende term in de rij het getal 2p+1.
Als die term t geen priemgetal is, dan is de volgende term zijn grootste echte deler < t.
Elke volgende term wordt met dit recept bepaald.
Een voorbeeld: 23 (priem), 2×23+1 = 47 (priem), 2×47+1 = 95 = 5 × 19, 19 (priem), … .
Dergelijke rijen kunnen zeer grillig verlopen.

Een lusrij
Dit is zo’n rij: 5, 11, 23, 47, 95, 19, 39, 13, 27, 9, 3, 7, 15, 5 en vanaf hier begint de rij zichzelf te herhalen. Deze rij is een lusrij te noemen zonder speciaal begin of eind. De kleinste term blijkt 3 te zijn.

Tijdens mijn onderzoek met verschillende begingetallen kwam ik steeds in de bovenstaande lusrij terecht.
Ik stopte steeds, als herkenningspunt, bij de 3.

Zijn deze rijen ooit eerder onderzocht en gedocumenteerd?

Ik vermoed, dat elke rij met gegeven voorschrift tenslotte in de genoemde lusrij terecht komt, ongeacht het begingetal.
Kun jij dat bewijzen of weerleggen?

Gebruikersavatar
Berichten: 701

Re: Een hardnekkige lusrij

Ik snap het nog niet helemaal maar ben je niet naar 'twin' primes opzoek (gap g=2)? Misschien helpt je dit verder zoeken.

Gebruikersavatar
Berichten: 3.540

Re: Een hardnekkige lusrij

Ik heb er ook een paar geprobeerd en kwam ook die drie tegen.

Heb je er een programmaatje voor geschreven, zodat je ze gemakkelijk kunt aflopen?

Gebruikersavatar
Moderator
Berichten: 4.838

Re: Een hardnekkige lusrij

De eerste dertig miljoen getallen komen uiteindelijk allemaal op 3 uit, in maximaal 45 stappen.

Gebruikersavatar
Berichten: 133

Re: Een hardnekkige lusrij

Als je er even over nadenkt, zal je inzien dat elk (samengesteld) getal altijd uitkomt op zijn grootste priemfactor.
Het is dus voldoende de priemgetallen te checken.
Vertrekken van dit priemgetal krijgen we eerst een cunningham-ketting van Sophie Germainpriemgetallen.
Als er een oneindige cunningham-ketting zou bestaan, zou dit betekenen dat we niet altijd op jouw cycle uitkomen. Maar er is niet geweten of er oneindig veel Sophie Germainpriemgetallen zijn...Ik geloof zelf dat een cunningham-ketting sowieso eindig is, moet ik nog eens opzoeken. Indien het laatste waar is, brengt het geen extra info over jouw probleem.
To be continued.

Gebruikersavatar
Moderator
Berichten: 4.838

Re: Een hardnekkige lusrij

De eerste honderd miljoen getallen komen uiteindelijk allemaal op 3 uit, in maximaal 47 stappen.

Geen van de getallen t/m 100.000.000 leidt tot een oneindige serie of een serie (lus) waar 3 niet in voorkomt.

Berichten: 247

Re: Een hardnekkige lusrij

Xilvo schreef: ma 18 jan 2021, 12:24 De eerste honderd miljoen getallen komen uiteindelijk allemaal op 3 uit, in maximaal 47 stappen.
Ik kom uit op 51 stappen voor 76 933 567:

Code: Selecteer alles

 0      76933567  prime
 1     153867135  comp    (div by 3)
 2      51289045  comp    (div by 5)
 3      10257809  prime
 4      20515619  prime
 5      41031239  prime
 6      82062479  prime
 7     164124959  prime
 8     328249919  prime
 9     656499839  prime
10    1312999679  comp    (div by 29)
11      45275851  prime
12      90551703  comp    (div by 3)
13      30183901  comp    (div by 11)
14       2743991  prime
15       5487983  comp    (div by 131)
16         41893  prime
17         83787  comp    (div by 3)
18         27929  comp    (div by 11)
19          2539  prime
20          5079  comp    (div by 3)
21          1693  prime
22          3387  comp    (div by 3)
23          1129  prime
24          2259  comp    (div by 3)
25           753  comp    (div by 3)
26           251  prime
27           503  prime
28          1007  comp    (div by 19)
29            53  prime
30           107  prime
31           215  comp    (div by 5)
32            43  prime
33            87  comp    (div by 3)
34            29  prime
35            59  prime
36           119  comp    (div by 7)
37            17  prime
38            35  comp    (div by 5)
39             7  prime
40            15  comp    (div by 3)
41             5  prime
42            11  prime
43            23  prime
44            47  prime
45            95  comp    (div by 5)
46            19  prime
47            39  comp    (div by 3)
48            13  prime
49            27  comp    (div by 3)
50             9  comp    (div by 3)
51             3  end
Ik vermoed dat jij
- niet het aantal stappen maar de lengte van de rij neemt
en
- niet de grootste echte deler < t maar de grootste priemdeler < t neemt ?

Gebruikersavatar
Moderator
Berichten: 4.838

Re: Een hardnekkige lusrij

Ik tel wel het aantal stappen maar ik neem inderdaad de grootste priemdeler.

Dat is inderdaad fout, in het eerste bericht volgt op 27 9. Dat is niet de grootste priemdeler maar de grootste deler<t.

Berichten: 433

Re: Een hardnekkige lusrij

Xilvo schreef: zo 17 jan 2021, 11:15 De eerste dertig miljoen getallen komen uiteindelijk allemaal op 3 uit, in maximaal 45 stappen.
Dank voor het proberen.
Dit is nog geen hard bewijs. Dat geeft geen enkele computer.
Maar het verstevigt wel het vermoeden.

Gebruikersavatar
Moderator
Berichten: 4.838

Re: Een hardnekkige lusrij

efdee schreef: ma 18 jan 2021, 14:31
Xilvo schreef: zo 17 jan 2021, 11:15 De eerste dertig miljoen getallen komen uiteindelijk allemaal op 3 uit, in maximaal 45 stappen.
Dank voor het proberen.
Dit is nog geen hard bewijs. Dat geeft geen enkele computer.
Maar het verstevigt wel het vermoeden.
In dit geval kan de computer inderdaad niets bewijzen.
Als hij tot een zekere grens vindt dat de rij uiteindelijk op 3 uitkomt weet je niet of dat voor alle getallen geldt.
Als hij niet op drie uitkomt binnen een afzienbaar aantal stappen dan is dat nog geen bewijs dat hij er nooit komt, dat die rij inderdaad oneindig is zonder herhalingen.
Het zou wel leuk zijn een andere lus te vinden waar 3 dan niet in zit.

Zoals RedCat schreef, ik gebruikte niet de juiste methode. Ik ben opnieuw begonnen en heb het programma wat efficiënter gemaakt.

Tot nu toe heb ik de eerste 27 miljoen getallen geprobeerd waarbij ik steeds in maximaal 49 stappen op 3 uitkwam.

Gebruikersavatar
Moderator
Berichten: 4.838

Re: Een hardnekkige lusrij

Nu met de correcte procedure:
De eerste tweehonderd miljoen getallen komen uiteindelijk allemaal op 3 uit, in maximaal 52 stappen.

Gebruikersavatar
Berichten: 701

Re: Een hardnekkige lusrij

Hallo,

Ik heb een flow diagram gemaakt van de series.

Aanvankelijk wilde ik de kansen uitrekenen. Kans op priemgetal ja/nee: middels: 1/ln(x). Vervolgens de grootste deler bepalen. Delen door eerst: 2, 3, 4, 5 etc. De grootste deler is dan x/2 bijvoorbeeld. Een soort hyperbool van kansen.

Echter kans rekeningen zijn niet direct nodig. Men komt nooit in een lus terecht waar de getallen kleiner kunnen worden.

Niet priem tak:
Kleinste in: 4 kan alleen voorkomen als start getal.
Kleinste in: 6
Kleinste uit: 3

Priemtak:
Kleinste in: 3
Kleinste uit: 5

Over de rest moet ik verder nadenken.

Het product: 2*3=6 (eerste priemgetallen) een priemgetal is dan volgens mij altijd +1 of -1 van een veelvoud van 6.

De kleinste input niet priemtak is 6 en heeft als output 3.
Nummer Lus.jpg

Berichten: 247

Re: Een hardnekkige lusrij

De eerste honderd miljard (= 10^11) getallen komen uiteindelijk allemaal op 3 uit.

Omdat elk samengesteld getal n in (bigomega(n) - 1) stappen uitkomt op zijn grootste priemdeler hoeven we alleen de priemgetallen te checken (zie ook Bart23 hierboven).
Van 2, 3 en 5 weten we al dat ze op 3 uitkomen.
Check steeds het volgende priemgetal p, te beginnen met p=7.
Zodra de rij vanuit het huidige priemgetal p uitkomt op een getal n kleiner dan p, weten we zeker dat n op 3 uitkomt (als n samengesteld is, dan is zijn grootste priemdeler zeker kleiner dan p; is n priem, dan is dat een kleiner priemgetal dan p, en we hebben al gecheckt dat de priemgetallen kleiner dan p allemaal op 3 uitkomen).
Dus ook p behoort tot de priemgetallen die op 3 uitkomen.

Roep onderstaande functie check3(p) aan voor alle priemgetallen.
Voor geen enkel priem p < 10^11 loopt deze functie vast, dus bereiken al de getallen < 10^11 uiteindelijk het getal 3.

Dit betekent ook: als er een lus zou bestaan die NIET op 3 belandt, het kleinste priemgetal van die lus groter dan 10^11 is.

Code: Selecteer alles

check3(priem p)
{
n=2*p+1;
while(n>=p){
  if(n is priem)
    n = 2*n+1
  else
    n = grootste priemdeler van n
  }
}
Parallel uitgevoerd in blokken van 20*10^9 getallen zijn binnen 5 uur alle priemgetallen < 10^11 gecheckt.

Gebruikersavatar
Berichten: 3.540

Re: Een hardnekkige lusrij

Ik zit me af te vragen of er wel een bewijs (als het klopt) te leveren is.

In het bewijs zou waarschijnlijk iets moeten zitten, dat toets of een getal al dan niet priem is.
Daar is eigenlijk geen formule voor, waar mijn formule op is gebaseerd.

Het is geen bewijs maar slechts een vermoede, want er bestaan ook stellingen over priemen zonder ze te toetsen.

Reageer