Den store project euler tråden

[Senyor de la guerra]

Liten forbedring nå, men må jo likevel prøve ett og ett nummer, blir jo ren "gjettelek".

 

 

 

	n = input('');

kvtall = sum(1:n)
a = 0;

for i = 1:kvtall
	if mod(kvtall, i) == 0
		a = a + 1;
	end
end

a

Tar likevel en liten evighet å regne ut tall over 1000. Altså en så og si ubrukelig kode

 

 

 

Edit: Surrer nå, dette var jo problem nr. 12.

 

Edit2: Finnes det noen innbygd funksjon i MATLAB som kan faktorisere 28 til 1,2,4,7,14,28.

 

 

Den jeg vet om faktoriserer slik:

>> factor(28)
ans =

  2   2   7

>>

 

 

Endret 6. januar 2010 av runesole

[zotbar1234]

Edit: Surrer nå, dette var jo problem nr. 12.

 

#12 var veldig morsom, og jeg bruke masse tid på den, og det første utkastet var dessverre langt i fra raskt.

 

 

 

Tips #1 vi trenger å regne ut alle divisorer til et tall. Hva kan man si om divisorer til N som er større enn sqrt(N)? Kan dette utnyttes for å forbedre kjøretiden til divisorberegningen? Ekstrahint: for divisorer av 28, trenger du ikke å *regne ut* 7, 14 eller 28.

 

Tips #2 Slike triangle tall kan regnes ut vha en formel -- gitt her.

 

Tips #3 Hva kan man si om divisorer til x og x+1 for to vilkårlige positive heltall x? (eller, rettere sagt, hvor mange divisorer har x og x+1 til felles?)

 

Disse tips tilsammen gir:

$ python ~/src/projecteuler.net/problem-012/problem12.py

puzzle 12, solution: <sensur> (in 0.274605s)

 

 

Endret 6. januar 2010 av zotbar1234

[Senyor de la guerra]

Tips #1:Må vel vite alle faktorene når det er det oppgaven går ut på å finne?

 

Tips #2: Funker slik med MATLAB:

>> sum(1:7)
ans =  28
>>

 

Tips #3: ... tenke

Endret 6. januar 2010 av runesole

[zotbar1234]

Tips #1:Må vel vite alle faktorene når det er det oppgaven går ut på å finne?

 

Nei, egentlig ikke -- man må *telle* hvor mange det er, ikke *hvilke* det er. Dvs det holder å vite at 28 har 6 divisorer. Vi trenger *ikke* å vite *hva* disse 6 divisorer er.

 

Tips #2: Funker slik med MATLAB:

>> sum(1:7)
ans =  28
>>

 

Tips 2 og 3 må sees på under ett At matlab har en ferdig funksjon for det er litt uvesentlig. Tipset er språkuavhengig.

[snippsat]

Kode:

 

 

clear
j = 20;
D = 1;

while D != 0

	for i = 1:20
			A(i) = mod(j, i);
	end

	D = sum(A);
	j = j + 20;

end

disp(j-20)

 

 

 

Ganske sikker på den stemmer, da jeg får rett svar for tall opptil 10.

!= er vel ~= i matlab?

Merker jeg rusten i matte

Da kjøre koden din greit oss meg,ca 50sek.

Et tips til euler 5 er least_common_multiples

 

Euler 5 matlab,da går det unna.

num = 11;
for i = 12:20
  num = lcm(num, i);
end

[Deneb]

@Jann_Ove: Takk, det korter tiden ned til ca 1,5 timer. Vet ikke hvordan jeg skal gå frem for å lære meg python.

 

 

Føkk Matlab

 

Den klarte jeg faktisk å bruteforce på 30 sekund i matlab. Men det var kanskje ikke problem 15 - du hadde skrevet feil? Si ifra om det var nr 15 og om du vil ha tips

[snippsat]

Vet ikke hvordan jeg skal gå frem for å lære meg python.

A Byte of Python er en god start.

 

Book er Beginning Python: From Novice to Professional bra.

Skrevet av Magnus Lie Hetland(NTNU)

Også Instant-Hacking på siden hans er en rask innføring i python.

[Senyor de la guerra]

Lykke:

>> clear
>> for i = 1
> tic
> euler14
> toc
> end
makslengde =  525
nmax =  837799
Elapsed time is 7558.525 seconds.
>>

 

Elapsed time is 7558.525 seconds.

[zotbar1234]

Lykke:

(...)

Elapsed time is 7558.525 seconds.

 

Ufff :!:

[Deneb]

Vis koden da

[zotbar1234]

Vis koden da

 

For hvilken av oppgavene?

[Deneb]

Tenkte på Runesole, var ekstrem tidsbruk. Artig å sammenligne med min egen.

[Senyor de la guerra]

 

 

>> type euler14
euler14 is the user-defined function defined from: C:\***\euler14.m

makslengde = 0;
nmax = 0;

for n = 1:1000000

	teller = n;
	A = [];
	A(1) = n;
	k = 2;

	while n > 1

			if round(n/2) != n/2
					n = 3*n + 1;
			else
					n = n/2;
			end

			A(k) = n;
			k = k + 1;

	end

	lengde = length(A);

	if makslengde < lengde
			makslengde = lengde;
			nmax = teller;
	end

	n = teller;

end

makslengde
nmax
>>

 

 

[Senyor de la guerra]

Etter å ha rappet en funksjon som lager finner alle divisorer ble prob 12 veldig lett

 

 

 

flagg = true;
n = 1;

while flagg

kvtall = sum(1:n);
	l = length(divisor(kvtall));
	if l > 500
		flagg = false;
	end
n = n + 1;
end

kvtall

 

 

 

Da er 13 problemer løst

Noen som vet hva "12 more until first level" vil si?

[GeirGrusom]

Lykke:

>> clear
>> for i = 1
> tic
> euler14
> toc
> end
makslengde =  525
nmax =  837799
Elapsed time is 7558.525 seconds.
>>

 

Elapsed time is 7558.525 seconds.

W00t? Hvordan fikk du så horribel ytelse?

 

524

837799

finished in 3450 ms

 

Jeg mer eller mindre blåkopierte koden din i C#.

[Senyor de la guerra]

Kjører på 1,4 GHz (Intel), 4GB RAM, gjennom Octave

Som sagt: Føkk MATLAB

Endret 7. januar 2010 av runesole

[zotbar1234]

Etter å ha rappet en funksjon som lager finner alle divisorer ble prob 12 veldig lett

 

Hvor rappet du den?

 

 

flagg = true;
n = 1;

while flagg

kvtall = sum(1:n);
	l = length(divisor(kvtall));
	if l > 500
		flagg = false;
	end
n = n + 1;
end

kvtall

 

 

 

 

- Den viktigste observasjonen er at en funksjon som regner antall divisorer av N ikke trenger å sjekke større tall enn sqrt(N) -- når 4 er en divisor av 28, så vil også 28/4 = 7 være det. Dette betyr at for hver divisor i intervallet [1,ceil(sqrt(N))) du finner, legger du 2 til antall divisorer funnet hittil. Det kreves en liten justering for tall som er kvadrater, opplagt, men dette er ideen.

 

- Den andre viktige observasjon er at alle trekanttall er på formen (x*(x+1))/2 (hvorfor det?) OG, siden gcd(x,x+1) = 1, så har ikke x eller x+1 noen divisorer til felles. Dvs. gitt et trekanttall N = (x*(x+1))/2, så er antall divisorer av N lik divisors(x) * divisors(x+1).

 

Disse to tilsammen gjør at man bruker godt under 1 sekund med tid. Det er nettopp den type observasjoner som gjør det mulig å løse enhver oppgave selv i språk uten raske (ift. standard C/Fortran) implementasjoner på i verste fall noen få sekunder. Bruce force er så å si *aldri* løsningen. Mao, det er *ikke* matlab som er problemet -- matlab er mer enn rask nok til samtlige av oppgavene.

 

 

Endret 7. januar 2010 av zotbar1234

[Senyor de la guerra]

Har de fleste språk en innebygd fn. for å vise alle divisorene?

[zotbar1234]

Har de fleste språk en innebygd fn. for å vise alle divisorene?

 

Dette er totalt uvesentlig -- man skriver en selv, soklart. Mathematica har f.eks. veldig mye stæsj tilgjengelig (som er garantert veldig veldig optimalisert), men det er aldri interessant. Etter hver skriver man en liten euler-modul med antall divisorer, liste av primtall og alle de andre oppgavene som dukker opp "ofte".

[Senyor de la guerra]

Neida, det gjør man ikke..