productless

Heb je een leuke wiskunde puzzel of een mooi vraagstuk gevonden en wil je die met ons delen? Post het hier.
Plaats reactie
David
Moderator
Moderator
Berichten: 4927
Lid geworden op: 14 mei 2009, 16:22

productless

Bericht door David » 14 mei 2014, 14:08

Een positief geheel getal is productless als het product van de cijfers kleiner of gelijk is aan de som van de cijfers. Bijvoorbeeld 1241 is productless want 1*2*4*1 <= 1+2+4+1. Hoeveel getallen kleiner dan een miljard zijn productless?
Stap 1 van het oplossen van een probleem is te erkennen dat je een probleem hebt.
(Raffiek Torreman)

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: productless

Bericht door arie » 15 mei 2014, 17:09

Leuk probleem.

Een mooie uitdaging voor pen en papier.
Met bovengrens 10^9 kom ik uit op 564154676.

Met bovengrens 10^100 op 9999701184262514640884493871012709747919817112365764931192028603168043520947736035044131458461887112
(maar dan wel m.b.v. de computer).

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: productless

Bericht door arie » 17 mei 2014, 09:47

Met bovengrens 10^(10^9) is het aantal getallen zonder nul erin:
11293504276630717799719633509069738955250472240017665619757028982153651344671394
39111269095660719389308010717972845185598769023828804989410364664368568048387862
80574380709669458913090527948975817648693246783572936581909919257416559865888107
en het aantal met 1 of meer nullen erin:
10^(10^9) - (9^((10^9)+1)-1)/8

De vraag is dan natuurlijk: kunnen we nog verder komen?

David
Moderator
Moderator
Berichten: 4927
Lid geworden op: 14 mei 2009, 16:22

Re: productless

Bericht door David » 18 mei 2014, 20:30

:shock: tot een miljard cijfers!

Ik heb een implementatie in VBA excel. Daarmee lukt het om het aantal zonder nullen tot 10^57 bepalen (484359270 kom ik uit). Pari lukte niet helemaal want ik kan niet de karakters in een string ophalen.

Laat A de verzameling zijn van positieve gehele getallen die geen 0 of 1 bevatten en waarvan de cijfers in aflopende volgorde staan. Dan, A = {2, 3, ..., 8, 9, 22, 32, 33, ...}. De score van een element uit A is het aantal cijfers dat nodig is voor een getal om die cijfers te bevatten. Dus de score van 32 is 3, want je hebt tenminste 3 cijfers nodig zodat 3 en 2 cijfers zijn van dat getal.

Dan bereken ik eerst de eerste veel elementen uit A, sorteer ze op score en dan het rijtje aflopen. Is dat ook ongeveer jouw methode?
Stap 1 van het oplossen van een probleem is te erkennen dat je een probleem hebt.
(Raffiek Torreman)

Sjoerd Job
Vergevorderde
Vergevorderde
Berichten: 1144
Lid geworden op: 21 jan 2006, 15:09
Locatie: Krimpen aan den IJssel

Re: productless

Bericht door Sjoerd Job » 19 mei 2014, 05:32

arie schreef:Leuk probleem.

Een mooie uitdaging voor pen en papier.
Met bovengrens 10^9 kom ik uit op 564154676.

Met bovengrens 10^100 op 9999701184262514640884493871012709747919817112365764931192028603168043520947736035044131458461887112
(maar dan wel m.b.v. de computer).
Al die grote getallen zijn goed en wel, maar heb je ook de antwoorden voor 10, 100, 1000, 10000, t/m 10^8 (ofzo), welke je hebt berekend op dezelfde manier?

Dit zodat ik naast jou antwoord een brute-force implementatie kan leggen, en kijken of je gevonden antwoord ook inderdaad correct is.

De theorie achter je antwoord zal waarschijnlijk wel goed zijn, maar toch handig om het te testen tegen antwoorden op een andere manier verkregen.
``Life is complex. It has real and imaginary parts.''

arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: productless

Bericht door arie » 19 mei 2014, 13:09

Hier een tabel met voor een aantal bovengrenzen (= 10^n):
[1] het aantal getallen zonder nul erin (=nz) dat voldoet aan de eis van David, en
[2] het totaal aantal getallen dat hieraan voldoet:

Code: Selecteer alles

10^n    nz         totaal
10^1:   9          9
10^2:   27         36
10^3:   61         241
10^4:   124        2743
10^5:   255        33825
10^6:   474        402603
10^7:   860        4620020
10^8:   1597       51574036
10^9:   2726       564154676
10^10:  4232       6077371781
10^11:  6741       64696314681
10^12:  10391      682266781850
Voor max = 10^57 kom ik net als David uit op nz = 484359270
(en in totaal 997226835956922174058004352114954313210290932674037058180 getallen)

Methode:

Alle getallen met 1 of meer nullen erin voldoen: het product van de cijfers is dan nul en daardoor altijd kleiner dan de som van de cijfers.

Als we kijken naar getallen van precies i cijfers (i>0):
- zijn dat er in totaal 9*10^(i-1): voor het eerste cijfer heb je keuze uit 9, de overige keuze uit 10
- zijn dat er zonder nul erin: 9*9^(i-1): in dit geval hebben we voor alle cijfers keuze uit 9
- het aantal met 1 of meer nullen is dus 9*10^(i-1) - 9*9^(i-1)

=> met bovengrens van 10^n is het aantal getallen met 1 of meer nullen erin =









Dit aantal is voor elke n relatief eenvoudig uit te rekenen, we kunnen ons daardoor beperken tot het aantal getallen zonder nul (nz) dat voldoet (zoals het getal 1241 gegeven door David).


Algoritme in hoofdlijnen:

Voor een bovengrens tot ongeveer 10^100 (= tot n = 100 cijfers) heb ik gewerkt met een tabel:
een matrix M[j] waarbij i het product en j de som van cijfers voorstelt.
M[j] is het aantal nz getallen met cijferproduct = i en cijfersom = j.

Voor 100 cijfers heeft de matrix afmetingen 900 x 900:
- de som van 100 cijfers is maximaal 900
- als het product groter wordt dan 900, dan hebben we die getallen niet meer nodig: dat product kan dan nooit meer kleiner of gelijk worden aan de maximale som = 900 (alle cijfers zijn nu >= 1).

Begin (=initialiseer) met bijvoorbeeld getallen van 1 cijfer:
- nz = 9
- M[1..900][1..900] = 0, behalve voor k=1 t/m 9: M[k][k] = 1

Dan herhaal voor elk volgend cijfer erbij:

Code: Selecteer alles

N[1..900][1..900]=0
voor elke i
    voor elk cijfer c = 1 t/m 9:
        p = c * i
        als p<=900 dan:
            voor elke j
                N[p][c + j] += M[i][j]
M = N
voor elke i
    voor elke j >= i
        nz += M[i][j]
(N is een tijdelijke matrix even groot als M)

Sjoerd Job
Vergevorderde
Vergevorderde
Berichten: 1144
Lid geworden op: 21 jan 2006, 15:09
Locatie: Krimpen aan den IJssel

Re: productless

Bericht door Sjoerd Job » 20 mei 2014, 16:35

Ik heb de kleine antwoorden geverifieerd met mijn 'trage' aanpak. Ze kloppen, dus ik heb hierbij vertrouwen in jullie aanpak.
``Life is complex. It has real and imaginary parts.''

David
Moderator
Moderator
Berichten: 4927
Lid geworden op: 14 mei 2009, 16:22

Re: productless

Bericht door David » 20 mei 2014, 18:49

Mijn Pari-implementatie is wat verder nu. Een semi-bruteforce werkt denk ik, voor alle resultaten krijg ik hetzelfde als Arie. Het lukt me alleen nog niet om snel grotere getallen te krijgen. Eerst was het ruwweg: bereken alle getallen in A, maar je kan er een hoop overslaan. Daarvoor heb ik bijna een implementatie maar hij slaat net iets teveel over. Bijvoorbeeld, voor het aantal nz voor 10^(10^9) krijg ik
11293504276626966915342297725070458441511293096072052767467776232668674447254674
78854547178803186677445190454777752149748403592924557196138923908616408065159006
96007096297735371453982135636879805219740538657718183998034685759623103086460938

(het verschilt na 12 cijfers achter de komma).

Voor 10^(10^12) krijg ik
49003325148175884078973730997644457242203612768466559098342861194271080580906264
50676052235815285094563797596589605232653661026880702740393382050502396479142141
66568181269267910719222721904191182052569137200546145136321301709955359269038624
06959657605894173595078513513143844495127693199611401394667926781366442950475584
81669704393328207926493785158483453218355894239485241750363083213644484866817665
1016477901514992436584021245323877

Gelukkig neemt de rekentijd niet ontzettend snel toe, ruim 4,5 sec. voor 10^(10^9) vs. ruim 29 sec. voor 10^(10^12).

Dit kan misschien sneller door niet alle elementen in A met minder dan 10 cijfers te doorlopen, voor 10^(10^9) maar gelijk het aantal getallen dat het bijdraagt te bepalen. Alleen daarvoor heb ik nog geen formule gevonden. Maar eerst alle nodige elementen in A aflopen.
Stap 1 van het oplossen van een probleem is te erkennen dat je een probleem hebt.
(Raffiek Torreman)

David
Moderator
Moderator
Berichten: 4927
Lid geworden op: 14 mei 2009, 16:22

Re: productless

Bericht door David » 26 mei 2014, 11:43

Mijn implementatie is werkend. Hier is de methode met de oorspronkelijke opgave als voorbeeld.

Als een getal productless is, is het product van de cijfers kleiner of gelijk aan de som. Dus zijn alle getallen die we vinden door de cijfers te herschikken ook productless. Bijvoorbeeld 321 is productless dus 123, 132, 213, 231 en 312 ook productless.
Zoals Arie al vaststelde, voldoen alle getallen waar minstens een cijfer een 0 zit. De beschrijving is voor productless getallen zonder 0 erin.

Eerst onderzoeken we de set A. Alle cijfers van A zijn van 2 t/m 9, met cijfers in aflopende volgorde.
Stel is het element in zodat elementen in kleiner zijn dan
Dan , , .
Stel nu de cijfers van , de cijfers aan elkaar gekoppeld. Voor hebben we dan
Het blijkt dat elementen hoogstens m cijfers hebben. Daar maken we gebruik van.
Om te vinden schrijven we i eerst in de vorm

Hier een voorbeeld voor het bepalen van
wordt zo gekozen dat maar . We kiezen m "maximaal".
Voor vinden we dan .
Dan verminderen we i met geeft n = 83 - 45 = 38.
Dus schrijven we 38 in de vorm. Omdat heeft drie cijfers

We bepalen , door die maximaal te kiezen en dan n verminderen met , dan evenzo en .
We vinden dat En dus
.
Dan gebruiken we de relatie tussen en , .
We vinden dan
Dus . Je zou kunnen stoppen met het bepalen van als n = 0, de cijfers zijn 2 vanaf dan.

Als achter een getal een 1 wordt gezet, neemt de som van de cijfers toe met 1, maar het product blijft gelijk. Dus als een getal productless is, kunnen we zoveel enen erachter plakken als we willen en dan is het resultaat nog steeds productless. Hier maken we gebruik van door de score te bepalen van een element in A.
De score van een element in A is het aantal cijfers dat minstens nodig is om die cijfers te bevatten.
is niet productless want 3 * 2 > 3 + 2. Als we een 1 achter 32 plakken, krijgen we 321. Dit is productless want 3 * 2 * 1 <= 3 + 2 + 1. De score van 32 is dus 3, want 321 heeft 3 cijfers.
Op vergelijkbare manier vinden we dat 742 een score heeft van 46.
7 * 4 * 2 = 56. 7 + 4 + 2 = 13. Er moeten nog minstens 56 - 13 = 43 enen achter worden geplakt voor een productless getal.
De score van een element in A met m cijfers is dus

Hoeveel productless getallen kleiner dan 10^9 bevatten nu alleen 32 en voor de rest enen?
De cijfers van 32 kunnen op 2 manieren worden gerangschikt.
321 voldoet, net als 3211, 32111, 321111, 3211111,...,321111111 net als alle herschikkingen van de cijfers.
Als we de cijfers 32 in die volgorde laten staan, dan zijn er mogelijke herschikkingen van de cijfers van 321; 132, 312 en 321. We vermenigvuldigen met 2 want 32 kan op 2 manieren worden gerangschikt.
Vergelijkbaar vinden we dat voor 3211 herschikkingen zijn, zodat we voor 32 een totaal van
vinden.
Om die som te vinden kunnen we gebruik maken van de volgende identiteit:


Zodat


Om het aantal permutaties van 32 of ook van grotere elementen van A te bepalen, bijv. 99888777755555 kan op minstens twee manieren.
- Bepaal het aantal cijfers m van a in A. Er zijn hoogstens m! herschikkingen. Voor elk uniek cijfer, deel door de frequentie van dat cijfer in a.
9 komt 2 keer voor, dus voor 9, deel door 2!. Het resultaat is .
- Stel (lokaal) n = 0, k = 0, r = 1. r is het resultaat. Voor elk uniek cijfer, tel bij n de frequentie op. stel k is de frequentie.
Dit geeft voor 99888777755555 (bijvoorbeeld, hangt van de volgorde van zoeken naar unieke cijfers af)
.

We kunnen proberen om alle elementen in A af te lopen, maar A heeft oneindig veel elementen, en we hoeven niet eens alle elementen af te lopen,
want we kijken naar een totaal van hoogstens 9 cijfers, ofwel de score van een element uit A mag hoogstens 9 zijn.
Hoeveel cijfers kan a in A dan maximaal hebben?
Als a hoogstens 1 cijfer heeft, dan werkt a = 2 nog, maar a = 22 niet. Als a hoogstens 2 cijfers heeft, dan werkt a = 22 nog maar a = 222 niet.
2 heeft een score van 1.
22 heeft een score van 2
222 heeft een score van 2*2*2 - (2+2+2) + 3 = 5
2222 heeft een score van 12. 12 > 9 Dus a heeft hoogstens 3 cijfers.
Algemeen, Een getal met n tweeën heeft een score van 2^n - 2*n + n = 2^n - n.
Voor maximaal q cijfers,
Om 2^n - n te verhogen naar 2^n, moeten we bij q nog optellen.
Dan geeft
Behalve als q <= 2, dan moet nog 1 worden opgeteld.

We kunnen nu dus alle elementen in A aflopen die hoogstens 3 cijfers hebben. Dat zijn er ,
maar we kunnen er veel overslaan. Dit gedeelte vond ik het lastigst.
Bijvoorbeeld, 63 heeft score 11, dus hoeven we 64, 65 en 66 niet te checken, en kunnen we door naar 72. 72 werkt, maar 73 niet dus kunnen we door
naar 82.

Mijn methode hiervoor is als volgt:
Zoek de plaats van het teken voor de eerste 2. Als er geen twee is, is het de laatste plaats. Voor 99992222 is dat 3. Voor 33 is dat 2. De variabele is y.
Zoek de plaats na de laatste 9. Als er geen 9 is, is het 1. Voor 99992222 is het 5. Voor 33 is het 1.
Bepaal y - t. Is het groter dan 0, dan, kijk naar het cijfer links van y. Verhoog het eerste cijfer van links dat hetzelfde is
als met 1. Alle cijfers rechts daarvan worden 2.
Als het niet groter dan 0 is, verhoog het aantal cijfers met 1 en maak elk cijfer 2. Als we van naar willen gaan
kan dat op vergelijkbare manier.
Stap 1 van het oplossen van een probleem is te erkennen dat je een probleem hebt.
(Raffiek Torreman)

Plaats reactie