Daar was ik eerst ook zeer verwonderd over, maar ik denk te weten hoe het komt...wnvl schreef:[Met PARI GP? Zou mij verwonderen dat ze numdiv zo inefficiënt hebben geïmplementeerd.
Is in jou implementatie de ontbinding in factoren ook meegerekend of vertrek je van de exponenten van de verschillende priemfactoren?
Als ik numdiv gebruik, dan moet ik die functie loslaten op n^2
Code: Selecteer alles
print(sum(n=1,10^6,(numdiv(n^2)+1)/2))
Code: Selecteer alles
{
som=0;
for(i=1,1000000,
f=factor(i);
l=length(f~);
som+=(prod(n=1,l,2*f[n,2]+1)+1)/2;
);
print(som);
}
Aha... op die manier... Daar moet zeker iets mee aan te vangen zijn. Alleen loop ik nog een beetje vast op de manier om bepaalde koppels wel of niet mee te tellen.wnvl schreef: We gaan dus niet alle getallen kleiner dan 10^6 een voor een ontbinden maar zoeken alle koppels die een kgv kleiner dan 10^6 hebben.
Een afbeelding voor n=20
rij=1 -> f(n)=n
rij=2 tot n/2 -> beetje rekenen; ik zie er wel een bepaald ritme in, maar dat moet nu nog in een algoritme gegoten worden
rij=n/2+1 tot n -> f(n)=1
Op die manier wordt het aantal rijen dat berekend moet worden al gehalveerd. En ik heb het gevoel dat er nog wel wat vereenvoudigd kan worden.
De eerst volgende dagen ga ik weinig tijd hebben om er aan verder te werken, maar ik kom er zeker nog op terug!