WisFaq!

Linkse N digits van getal delen door N, uitkomst moet geheel getal zijn

Voor een hobby ben ik op zoek naar de formule en het programmeren hiervan om de oplossing van een probleem te vinden.
Het probleem luidt(en is te vinden op http://www.geocaching.com/seek/cache_details.aspx?wp=GC14yny):
===
Start your search for all numbers with over 14 digits, that fulfil a simple condition:
The number made by its leftmost N digits is divisible by N, where the quotient is a Natural number.
===
Ik heb zelf al flink met Excel en marco's/functies gestunteld, maar ben nog uit op snelle (ik heb iets geprogrammeerd waar uiteindelijk de oplossingen over enkele weken misschien uit zullen rollen) rekenmethode/oplossing gekomen.

Wie kan mij een beetje op weg helpen?

groet
Carsten

Carsten Weegels
23-8-2007

Antwoord

Ik doe het in ongeveer 0,05 seconden.

Ik vermoed dat jouw programma alle getallen van 14 cijfers controleert op de gevraagde eigenschap. Dat is natuurlijk enorme overkill: alle getallen met een oneven cijfer op de tweede plaats hoef je bijvoorbeeld al niet in rekening te brengen. Als je wat verder redeneert, zie je dat je dit best recursief kan aanpakken: als je een getal van n cijfers hebt dat voldoet aan de eigenschap, dan gebruik je dat als start voor mogelijke getallen van n+1 cijfers. Als dat getal van n cijfers niet voldoet, kan je ook onmiddellijk alle getallen van meer cijfers die met dit getal beginnen overslaan.

Voor cijfers op de n-de plaats zijn er trouwens hoogstens roundup(10/n) kandidaatcijfers, zodat blijkt dat het aantal getallen dat we effectief zullen controleren heel beperkt zal zijn.

Hieronder een codevoorbeeld in C. Het bepaalt alle getallen die voldoen aan de eigenschap van minder dan MAX_DIGITS cijfers en schrijft de getallen op het scherm als ze minstens START_DIGITS cijfers hebben, anders zijn er wat te veel resultaten. De vreemde functies zijn afkomstig van de GMP (GNU Multiprecision library), die ik nodig heb om met getallen van dergelijke grootte om te gaan.

#include <gmp.h>
#include <stdio.h>

const int MAX_DIGITS = 30;
const int START_DIGITS = 20;

void add_digit(mpz_t a, int n) {
        for (int j=0;j<9;j++) {
                mpz_t t;
                mpz_init_set(t, a);
                mpz_mul_ui(t, t, 10);
                mpz_add_ui(t, t, j);
                if ((mpz_divisible_ui_p(t,n+1) != 0) && (n<MAX_DIGITS)) {
                     
                if (n+1>=START_DIGITS) {gmp_printf("%Zd\n",t);};
                        add_digit(t,n+1);
                mpz_clear(t);
                }
        }
}

int main (void) {
        for (int j=1;j<9;j++) {
                mpz_t jj;
                mpz_init_set_ui(jj,j);
                add_digit(jj,1);
                mpz_clear(jj);
        }
}

met als uitvoer

christophe@saive ~ $ time ./digits
144408645048225636603
1444086450482256366038
14440864504822563660381
144408645048225636603816
240858882000105660207
2408588820001056602074
24085888200010566020746
306804483048705606405
360852885036840078603
3608528850368400786036
36085288503684007860367
360852885036840078603672
3608528850368400786036725
567252000048585618606
5672520000485856186064
663252885024660810201
726456564024105672408
7264565640241056724082
72645656402410567240820
741258081084360042000
7412580810843600420006
846804726024465672807
8468047260244656728072

real    0m0.049s
user    0m0.050s
sys     0m0.000s

Het grootste getal met de gevraagde eigenschap is dus 3608528850368400786036725, een getal van 25 cijfers. In totaal vind je 13746 getallen van 2 of meer cijfers.

cl
25-8-2007