productless

[drc.]

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?

[siep]

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).

[siep]

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?

[drc.]

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?

[Sjoerd Job]

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.

[siep]

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 =

\(\sum_{i=1}^{n} \left(9\cdot 10^{i-1} - 9\cdot9^{i-1}\right)\)

\(= 9 \cdot \sum_{i=1}^{n} 10^{i-1} - 9 \cdot \sum_{i=1}^{n}9^{i-1}\)

\(= 9 \cdot \frac{10^n-1}{10-1} - 9 \cdot \frac{9^n-1}{9-1}\)

\(=10^n - \frac{9^{n+1}-1}{8}\)

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]

Ik heb de kleine antwoorden geverifieerd met mijn 'trage' aanpak. Ze kloppen, dus ik heb hierbij vertrouwen in jullie aanpak.

[drc.]

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.

[drc.]

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 a_i is het element in A zodat n-1 elementen in A kleiner zijn dan a_n
Dan a_1 = 2, a_{10} = 32, a_{100} = 777.
Stel nu d_jd_{j-1}\cdots d_{1} de cijfers van a_n, de cijfers aan elkaar gekoppeld. Voor a_{10} hebben we dan d_2 = 3,\, d_1 = 2
Het blijkt dat {m + 8 \choose m} - 1 = {m + 8 \choose 8} - 1 elementen hoogstens m cijfers hebben. Daar maken we gebruik van.
Om a_i te vinden schrijven we i eerst in de vorm
{m + 8 \choose 8} + \sum_{j=1}^{m+1} {c_j \choose j}
Hier een voorbeeld voor het bepalen van a_{83}
m wordt zo gekozen dat {m + 8 \choose 8} \le i maar {m + 8 + 1 \choose 8} > i. We kiezen m "maximaal".
Voor a_{83} vinden we dan m = 2.
Dan verminderen we i met {m + 8 \choose 8} = 45 geeft n = 83 - 45 = 38.
Dus schrijven we 38 in de vorm. Omdat m = 2 heeft a_{83} drie cijfers
\sum_{j=1}^{m+1} {c_j \choose j}
We bepalen c_3, door die maximaal te kiezen en dan n verminderen met {c_3 \choose 3}, dan evenzo c_2 en c_1.
We vinden dat 38 = {7 \choose 3} + {3 \choose 2} + {0 \choose 1} En dus
c_3 = 7, c_2 = 3, c_1 = 0.
Dan gebruiken we de relatie tussen c_i en d_i, d_i = c_i + 3 - i.
We vinden dan d_3 = 7 + 3 - 3 = 7,\, d_2 = 3 + 3 - 2 = 4,\, d_1 = 0 + 3 - 1 = 2
Dus a_{83} = 742. Je zou kunnen stoppen met het bepalen van c_i 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.
a_10 = 32 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 \prod_{i=1}^{m}d_i - \sum_{i=1}^{m}d_i + m

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 {3 \choose 2} 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 2 \cdot {4 \choose 2} = 12 herschikkingen zijn, zodat we voor 32 een totaal van
\sum_{i=3}^{9} \left( 2 \cdot {i \choose 2}\right) vinden.
Om die som te vinden kunnen we gebruik maken van de volgende identiteit:

\sum_{i=m}^{n} {k \choose m} = {n + 1 \choose m + 1}
Zodat
\sum_{i=3}^{9} 2 \cdot {i \choose 2} = 2 \cdot \left(\left(\sum_{i=0}^{9} {i \choose 2}\right) - \left(\sum_{i=0}^{2} 2 \cdot {i \choose 2} \right) \right) = 2 \cdot \left( {10 \choose 3} - {3 \choose 3} \right) = 2(120 - 1) = 238

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 {14 \choose 2,3,4,5} = 2522520.
- 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)
{2 \choose 2} \cdot {5 \choose 3}\cdot {9 \choose 4}\cdot {14 \choose 5} = 2522520.

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 \lceil \frac{\log(q)}{\log(2)} \rceil optellen.
Dan geeft \lfloor \frac{q + \lceil \frac{\log(q)}{\log(2)} \rceil}{\log(2)} \rfloor
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 {11 \choose 8} - 1 = 164,
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 d_y 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 a_{i} naar a_{i+1} willen gaan
kan dat op vergelijkbare manier.