Kleinste of n{}

[efdee]

Kleinste of n{}

Met n{} definieer ik het kleinste getal dat deelbaar is door alle voorgangers van n en n zelf.
De voorgangers van n zijn 1, 2, 3, …, n-2 en n-1. Toegevoegd is n.

n 1 2 3 4 5 6 7 8 9 10 (Mijn spaties zijn hier weggelaten.)
n{} 1 2 6 12 60 60 420 840 2520 2520

n 11 12 13 14 15 (Hier zijn de spaties ook weggehaald.)
n{} 27720 27720 360360 360360 360360

Vraag a: heeft zo’n getal al een naam?
Vraag b: bestaat er al een ander symbool dan n{} ?
Vraag c: wat is het algemene recept voor n{} ?
Mijn poging om dat te verwoorden is deze:
bepaal alle voorkomende priemgetallen. Vermenigvuldig ze, elk voorzien van de hoogst voorkomende exponent.
is dat correct of te verbeteren?

[Xilvo]

Het is het kleinste gemene veelvoud van de getallen 1..n

1 1
2 2
3 6
4 12
5 60
6 60
7 420
8 840
9 2520
10 2520
11 27720
12 27720
13 360360
14 360360
15 360360
16 720720
17 12252240
18 12252240
19 232792560
20 232792560
21 232792560
22 232792560
23 5354228880
24 5354228880
25 26771144400
26 26771144400
27 80313433200
28 80313433200
29 2329089562800
30 2329089562800
31 72201776446800
32 144403552893600
33 144403552893600
34 144403552893600
35 144403552893600
36 144403552893600
37 5342931457063200
38 5342931457063200
39 5342931457063200
40 5342931457063200

[tempelier]

Ik denk dat er geen algemeen recept voor bekend is.

Er is immers ook geen recept voor Priemen bekend, wat hiermee verwant is.

[efdee]

Ik denk dat er geen algemeen recept voor bekend is.

Zie boven de rij voorbeelden:
het kgv vd getallen 1 t/m n.
Het ei van Columbus!

[tempelier]

Die voorbeelden zijn stuk voor stuk (opvolgend) met een of ander programma berekend.
Dat is iets anders als een recept een formule.

[Xilvo]

Een programma is een recept.

[Math-E-Mad-X]

Die voorbeelden zijn stuk voor stuk (opvolgend) met een of ander programma berekend.
Dat is iets anders als een recept een formule.

Dat hangt er helemaal vanaf wat je precies onder 'recept' verstaat. Zolang de topic starter dat niet aangeeft kunnen we niet zeggen of er wel of geen recept bestaat.

Uiteindelijk is een computer programma niets anders dan een (hele lange en ingewikkelde) formule.

[tempelier]

Computers vinden vaak antwoorden door domweg te proberen.

Dat is een barbaarse methode die niet hoog staat aangeschreven in de wiskunde.

[Xilvo]

Computers vinden vaak antwoorden door domweg te proberen.

Ook dan volgt de computer een recept.

Dat is een barbaarse methode die niet hoog staat aangeschreven in de wiskunde.

Soms is het de enige (bekende) methode.

[Math-E-Mad-X]

Computers vinden vaak antwoorden door domweg te proberen.

Dat is een barbaarse methode die niet hoog staat aangeschreven in de wiskunde.

Mee eens, maar dat neemt niet weg dat we eerst moeten weten wat de topic starter dan wel onder een recept verstaat.

In de literatuur wordt meestal het begrip closed-form expression gebruikt. Maar ook hierbij is het nog steeds belangrijk om op te merken dat:

The set of operations and functions admitted in a closed-form expression may vary with author and context.

[tempelier]

Computers vinden vaak antwoorden door domweg te proberen.

Dat is een barbaarse methode die niet hoog staat aangeschreven in de wiskunde.

Mee eens, maar dat neemt niet weg dat we eerst moeten weten wat de topic starter dan wel onder een recept verstaat.

In de literatuur wordt meestal het begrip closed-form expression gebruikt. Maar ook hierbij is het nog steeds belangrijk om op te merken dat:

The set of operations and functions admitted in a closed-form expression may vary with author and context.

Ik weet wel dat er verschillend over wordt gedacht en niet alleen hier over,
dat is echter vaak afhankelijk tot welk vak men behoort.

Een computerman zal het veel ruimer zien dan een wiskundige.
Het is echter wel gepost onder het onderwerp wiskunde, dus lijkt me het logisch dat als uitgangspunt te nemen.

PS.
Het verschil in instelling bleek uit de meest compacte bolstapeling (voordat ze bewezen was)

1. Wiskundigen vermoedde het.
2. Natuurkundigen dachten het.
3. Scheikundigen wisten het zeker.

(4. Programmeurs vonden het niet interessant)

[efdee]

Met een recept bedoel ik een voorschrift om tot een oplossing te komen.
Het is dan in mijn ogen een algoritme.

[Math-E-Mad-X]

Met een recept bedoel ik een voorschrift om tot een oplossing te komen.
Het is dan in mijn ogen een algoritme.

Maar de vraag is waar dat 'voorschrift' of 'recept' uit mag bestaan. Als het een computer programma mag zijn dat geschreven is in een taal zoals Java of Python, dan kun je gewoon een programma schrijven dat één voor één alle mogelijkheden uitprobeert tot hij het juiste antwoord vindt. In dat geval is het antwoord dus: "JA, er bestaat een recept." en dat recept is zelfs heel simpel.

Maar zoals opgemerkt, dat is niet echt een wiskundige oplossing, en de oplossing is bovendien zo triviaal dat het er op lijkt dat dit niet is waar je naar op zoek bent.

[OOOVincentOOO]

In de OEIS (integer series database) is deze serie te vinden meerdere entry's (met bijna vergelijkbare series). Ik heb de eerste entry vergeleken met lijst van Xilvo, lijkt te kloppen:

https://oeis.org/search?q=1%2C+2%2C+6%2 ... &go=Search

In de formule sectie is meer informatie te vinden met respect tot priemgetallen. Dit gaat bij boven mijn pet, en kan zo snel geen simpele uitleg vinden. Wel: a(n) = Product (p^(floor(log n/log p))) (p is priemgetal tot n)

Wel een rekenvoorbeeld hier wat ik wel kan volgen:

Example:
LCM of {1,2,3,4,5,6} = 60. The primes up to 6 are 2, 3 and 5. floor(log(6)/log(2)) = 2 so the exponent of 2 is 2.
floor(log(6)/log(3)) = 1 so the exponent of 3 is 1.
floor(log(6)/log(5)) = 1 so the exponent of 5 is 1. Therefore, a(6) = 2^2 * 3^1 * 5^1 = 60. - David A. Corneth, Jun 02 2017

[Erik Leppen]

het kleinste gemeenschappelijke veelvoud (kgv) van een verzameling positieve gehele getallen is per definitie het kleinste getal dat deelbaar is door al deze getallen. Om dat getal te vinden is het héél handig om de priemfactorisatie van die getallen te kennen.

Voorbeeld: stel je zoekt de kgv van 60 en 72. Vind dan eerst de priemfactorisaties van 60 en 72

\(60 = 2^2 \times 3^1 \times 5^1\)

\(72 = 2^3 \times 3^2 \times 5^0\)

Het kgv(60, 72) is een veelvoud van 60, en is dus deelbaar door 60, en is dus deelbaar door \(2^2\), door \(3^1\) en door \(5^1\). Het heeft dus minstens 2 factoren 2, 1 factor 3 en 1 factor 5.
Het is evenzo deelbaar door 72, en dus deelbaar door \(2^3\) en door \(3^2\). Het heeft dus minstens 3 factoren 2 en 2 factoren 3.

Een getal met al deze eisen heeft 3 factoren 2, 2 factoren 3 en 1 factor 5, en het kleinste heeft verder geen priemfactoren. Dat getal bedraagt dus:

\(2^3 \times 3^2 \times 5^1 = 360\)

Inderdaad is 360 deelbaar door 60 en 72: \(360 / 60 = 6\) en \(360 / 72 = 5\). De quotiënten hebben geen gemeenschappelijke delers (waarom?)

Dit werkt ook zo voor de kgv van méér dan 2 getallen. Voorbeeld: kgv(80, 84, 90)

\(80 = 2^4 \times 3^0 \times 5^1 \times 7^0\)

\(84 = 2^2 \times 3^1 \times 5^0 \times 7^1\)

\(90 = 2^1 \times 3^2 \times 5^1 \times 7^0\)

iets wat deelbaar is door \(2^4\) door \(2^2\) en door \(2^1\) is deelbaar door \(2^{\max{4, 2, 1}}\)
Dus je neemt voor elke exponent de hoogste van alle die voorkomen:

\(2^4 \times 3^2 \times 5^1 \times 7^1 = 5040\)

Dus dat is het algoritme: neem van alle priemfactoren in alle getallen, de hoogst voorkomende exponent.

Dan kgv(1, 2, ..., n). Ter voorbeeld kgv(1, 2, ..., 16):

\( 1 = 2^0 \times 3^0 \times \cdots\)

\( 2 = 2^1 \times 3^0 \times \cdots\)

\( 3 = 2^0 \times 3^1 \times \cdots\)

\( 4 = 2^2 \times 3^0 \times \cdots\)

\( 5 = 2^0 \times 3^0 \times \cdots\)

\( 6 = 2^1 \times 3^1 \times \cdots\)

\( 7 = 2^0 \times 3^0 \times \cdots\)

\( 8 = 2^3 \times 3^0 \times \cdots\)

\( 9 = 2^0 \times 3^2 \times \cdots\)

\(10 = 2^1 \times 3^0 \times \cdots\)

\(11 = 2^0 \times 3^0 \times \cdots\)

\(12 = 2^2 \times 3^1 \times \cdots\)

\(13 = 2^0 \times 3^0 \times \cdots\)

\(14 = 2^1 \times 3^0 \times \cdots\)

\(15 = 2^0 \times 3^1 \times \cdots\)

\(16 = 2^4 \times 3^0 \times \cdots\)

De reden dat ik het zo uitschrijf is dat je dan de regelmaat ziet in de exponenten.

Wat is de hoogste exponent van priemfactor 2 die voorkomt in 1 .. 16? Dat is 4, want \(2^4 <= 16\) en \(2^5 > 16\).
Wat is de hoogste exponent van priemfactor p die voorkomt in 1 .. n? Dat is die k zodanig dat \(p^k <= n\) en \(p^{k + 1} > n\).
En dat is dus \(\lfloor \log_{p}{n} \rfloor\) (de haken betekenen: afronden naar beneden (floor))

Conclusie: kgv(1, ..., n) heeft als priemfactoren alle priemfactoren in 1 ... n (dus alle priemgetallen \(\leq n\)), met als exponent de hoogst voorkomende exponent van p in 1 .. n, oftewel:
kgv(1, ..., n) = \(\prod_{p \leq n} p^{ \lfloor \log_{p}{n} \rfloor}\) voor alle priemgetallen p.