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
Carste
Iets anders - donderdag 23 augustus 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); } }
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.
