Minsta positiva heltalet n!
Hej!
Jag ska lösa denna uppgift:
Bestäm det minsta positiva heltalet n! som är delbart med 2^15
Det har kört fast sig för mig, vad kan jag börja med att göra?
Prova exempelvis att primtalsfaktorisera 6!, kan det ge någon ledtråd?
6! = 3*3*2*2*2*2*5, ska jag leta efter talet som innehåller 15st tvåor?
Supernova127 skrev:6! = 3*3*2*2*2*2*5, ska jag leta efter talet som innehåller 15st tvåor?
Ja, det minsta heltal n! som innehåller minst 15 st tvåor i sin primtalsfaktorisering. Läs gärna på lite om delbarhet för att förstå varför: https://www.matteboken.se/lektioner/matte-5/kongruensrakning/delbarhet
borde finnas en annan, mer effektiv metod eftersom att det inte går att bara pröva sig fram från 6 och uppåt. Redan vid 9 eller tio blir det extremt tidskrävande och dessutom hittar man inget tal som har 2^15 som produkt även om man går ända till n = 15. Jag vet faktiskt inte hur man skulle bära sig åt med denna uppgift men jag är väldigt nyfiken på hur en lösning skulle kunna se ut.
Det är enkelt att primfaktorisera varje faktor i samband med att man multiplicerar med den. Udda tal är intedelbara med 2, så man behäver inte undersöka 3!, 5! och så vidare
2! innehåller 1 faktor 2
4! tillför 2 faktorer 2, 3 totalt
6! innehåller 4 2or
8! innehåller 6 2or
10! innehåller 7 2or
12! innehåller 9 2or
14! innehåller 10 2or
16! innehåller 14 2or
18! innehåller 15 2or
klar!!!
EDIT: Oj, jag missade visst en 2:a i faktorn 8 men principen stämmer
Smaragdalena skrev:Det är enkelt att primfaktorisera varje faktor i samband med att man multiplicerar med den. Udda tal är intedelbara med 2, så man behäver inte undersöka 3!, 5! och så vidare
2! innehåller 1 faktor 2
4! tillför 2 faktorer 2, 3 totalt
6! innehåller 4 2or
8! innehåller 6 2or
10! innehåller 7 2or
12! innehåller 9 2or
14! innehåller 10 2or
16! innehåller 14 2or
18! innehåller 15 2or
klar!!!
8! borde ge 3 st 2:or
som jag tolkar det du skriver har du räknat med 2 st
järnkuken skrev:borde finnas en annan, mer effektiv metod eftersom att det inte går att bara pröva sig fram från 6 och uppåt. Redan vid 9 eller tio blir det extremt tidskrävande och dessutom hittar man inget tal som har 2^15 som produkt även om man går ända till n = 15. Jag vet faktiskt inte hur man skulle bära sig åt med denna uppgift men jag är väldigt nyfiken på hur en lösning skulle kunna se ut.
Går ju att effektivisera en del, till exempel som Smaragdalena har visat. Dessutom kan man ju återanvända sitt resultat. Eftersom exempelvis 8! = 8 * 7! blir det mycket lättare att ta fram primtalsfaktorerna för 8! om man redan tagit fram dem för 7!.
Dessutom behöver man inte bry sig om något annat än 2:orna. Det är egentligen för uppgiften helt ointressant hur många 3:or eller 5:or som finns i primtalsfaktoriseringen, det enda man behöver hålla koll på är hur många nya 2:or som tillkommer.
Så, om man vet att 6! innehåller 4 st 2:or, vet man att även 7! har lika många då 7! = 7 * 6! och 7 är udda. Sen kan man ta reda på att 8! har 7 st 2:or då .
