Tallteori

[Gustav]

Finn alle positive heltall $n<200$ slik at $n^2+(n+1)^2$ er et perfekt kvadrat.

[Emilga]

Er det juks å bruke python?

[Gustav]

Er det juks å bruke python?

Ja!

[Enrahim]

Prøver å unngå spoilere: Gøy oppgave! Trengte ikke kalkulator heller, unntatt for å teste svarene (og jeg hadde gjort noen slurvefeil), og så var jeg for lat så jeg tok 17*24 på kalkulator også. Pen følge Har ikke sjekket om det går an å finne et lukket form uttrykk for for den da.. men tviler på grunn av kvadratrøttene (en god tilnærminger er forøvrig ganske grei - der 3+2 sqrt(2) står sentralt ).

[Gustav]

Prøver å unngå spoilere: Gøy oppgave! Trengte ikke kalkulator heller, unntatt for å teste svarene (og jeg hadde gjort noen slurvefeil), og så var jeg for lat så jeg tok 17*24 på kalkulator også. Pen følge Har ikke sjekket om det går an å finne et lukket form uttrykk for for den da.. men tviler på grunn av kvadratrøttene (en god tilnærminger er forøvrig ganske grei - der 3+2 sqrt(2) står sentralt ).

Det er nå fritt fram å poste fullstendig løsning.

[Enrahim]

Kan skissere hovedideen jeg brukte: Det er nok å bruke andregradsformelen 2 ganger på to andregradsulikheter basert på at du skal få et fullstendig kvadrat når du får et tall som er større enn et grunntall (altså har formen (n+c)^2 der n og c er heltall), og merke at for at dette skal bli et heltall må det som er under rottegnet også være et fullstendig kvadrat. Du får da en flott rekursjon der du med utgangspunkt i den pytagoreiske trippelen 3,4,5 kan nøste opp alle løsninger.

[Hoksalon]

Mitt bidrag.

[tex]n^2 + (n+1)^2 = (n+a)^2[/tex]

[tex]2n^2 + 2n + 1 = n^2 + 2na + a^2[/tex]

*nerde*

[tex]n = a - 1 \pm \sqrt{2a(a-1)}[/tex]

Et litt tregt overslag gir oss at a ikke kan være større enn 90. Da gjelder det for min del bare å være forsiktig og undersøke alle mulige tilfeller som gir heltallige n. Da finner jeg at a = {2,9,50}, hvilket gir oss n = {3,20,119}.

EDIT: Ser fram til en bedre løsning. Jeg var i ferd med å ikke legge merke til a = 50.

[Nebuchadnezzar]

Code: Select all

 
    i                      m^2                   m
-------------------------------------------------------          
      3                     25                   5 
     20                    841                  29
    119                  28561                 169
    696                 970225                 985
   4059               32959081                5741
  23660             1119638521               33461
 137903            38034750625              195025
 803760          1292061882721             1136689

Hvor m^2 = i^2 + (i+1)^2, slik at dere som liker å regne for hånd har noe å gå etter..

[Hoksalon]

Code: Select all

 
    i                      m^2                   m
-------------------------------------------------------          
      3                     25                   5 
     20                    841                  29
    119                  28561                 169
    696                 970225                 985
   4059               32959081                5741
  23660             1119638521               33461
 137903            38034750625              195025
 803760          1292061882721             1136689

Hvor m^2 = i^2 + (i+1)^2, slik at dere som liker å regne for hånd har noe å gå etter..

Hekseri og trolldom! Jeg stemmer for vannprøve.

[Nebuchadnezzar]

http://pastebin.com/hdt3WgPc

[mrcreosote]

http://pastebin.com/hdt3WgPc

Oppgava minner om denne, og "løsningene" er bare nesten-løsninger, sannsynligvis fordi beregningene ikke er gjort med tilstrekkelig presisjon. For eksempel er [tex]10348623402^2=7317581783^2+7317581784^2-28141[/tex]. Nært, men ingen rull av tørkede tobakksblad til å røyke på.

[Nebuchadnezzar]

Code: Select all

function Liste = Plutarco( N )

               k = 1;
    Liste        = zeros(1000,2);  
    Liste(k,1:2) = [0;1]; 
    
while Liste(k,1) < N   
    Liste(k+1,1:2) = Liste(k,1:2) * [3 4; 2 3] + [1,2];
    k = k + 1;
end

    Liste( ~any(Liste,2), : ) = [];

[Enrahim]

Hoksalon: Startet på samme måte som deg, men metoden blir bedre dersom du fortsetter på samme måte med 2a(a-1)=(a+b)^2 Du får da etter akkurat samme nerdingen at a=b+1+sqrt(b^2+(b+1)^2) Fryd og gammen - det som er i parantesen er akurat de komplette kvadratene vi vil finne - og som om det ikke var nok så "lagger" de akurat 1 bak (b=0 gir n=3, b=3 gir n=20, b=20 gir n=119, b=119 gir n=696 osv). Hakket raskere og mer presis enn din, Nebuchadnezzar?

edit: enkel kortform - la n[0]=3 og a[0]=2 Da vil a[x+1] = 2*n[x] + a[x] + 1 og n[x+1] = 2*a[x+1] + n[x] - 1 (eller n[x+1]=5*n[x]+2*a[x]+1 for å få tydeligere frem at n vokser med en faktor omtrent mellom 5 og 7 for hvert steg)

[Nebuchadnezzar]

Nei Peke på den oppdaterte korrekte koden ovenfor

EDIT: La $n^2 + (n+1)^2 = m^2$, da er $m$ og $n$ definert rekursivt som

$\displaystyle
\begin{pmatrix}
n_k \\
m_k
\end{pmatrix}
=
\begin{pmatrix}
n_{k-1} \\
m_{k-1}
\end{pmatrix}
\begin{pmatrix}
3 & 4 \\
2 & 3
\end{pmatrix}
+
\begin{pmatrix}
1 \\
2
\end{pmatrix}
$,

hvor $n_0 = 0$, og $m_0 = 1$.

[Enrahim]

Nei Peke på den oppdaterte korrekte koden ovenfor

Ah, fikk ikke med meg i farten at det var en forbedret versjon