Problema dell'Euler di progetto 233

Question

Ho deciso di affrontare il Project Euler problema 233 successivo ma io sto avendo alcuni problemi importanti! Ho fatto alcune analisi e ho fatto dei progressi piuttosto interessanti, ma ora mi sono bloccato. Ecco il mio lavoro:

Lemma 1 : Poiché il cerchio attraversa i 4 punti d'angolo, ci sono almeno 4 soluzioni per ogni n. Ma per ogni punto sulla circonferenza ce ne sono altri 7 trovati con la riflessione. Pertanto ci sono sempre 8k + 4 punti reticolari.

Lemma 2 : Il cerchio ha raggio (v2) n e centro (n / 2, n / 2) quindi la sua equazione è (x-n / 2) ^ 2 + (y-n / 2) ^ 2 = [n / v2] ^ 2. Ciò si riduce a x ^ 2 + y ^ 2 = n (x + y).

Lemma 3 : Se viene scritta una soluzione di x ^ 2 + y ^ 2 = n (x + y) (x, y, z), un'altra soluzione è (kx, ky, kz). La prova di ciò è:

(x+y)n = x^2+y^2

(kx)^2+(ky)^2 = (kx+ky)m
k(x^2+y^2) = (x+y)m
m = kn

Questo era quanto ho fatto con quella linea di pensiero - non potevo vedere da nessuna parte andare da lì ma è incluso perché potrebbe essere utile.

Il mio prossimo pensiero fu di spostare il centro del cerchio. Ci sarà lo stesso numero di soluzioni spostandolo in qualsiasi dimensione di un intero numero intero. Quindi quando n / 2 è intero, quindi n = 2k, x ^ 2 + y ^ 2 = 2 * k ^ 2. E si scopre anche che ci sono tante soluzioni a questa equazione quante sono le equazioni x ^ 2 + y ^ 2 = k ^ 2 (vedi Sloane A046109 ).

Ciò fornisce anche un metodo semplice per calcolare il numero di soluzioni per qualsiasi n tramite A046080 . Se i poteri sui numeri primi in n della forma 4k + 1 sono f [0] ... f [m], il numero di soluzioni è 4 * prodotto (2f [i] +1 | i in [0 .. .m]).

Questo mi ha permesso di lavorare all'indietro: 4.product (2f [i] +1 | i in [0 ... m]) = 420, quindi product (2f [i] +1 | i in [0 .. .m]) = 105 = 3 * 5 * 7. Sono stato in grado di escogitare questo programma che penso trova la somma di tutti n, nella forma 2k e inferiore a 10 ^ 11, che hanno 420 punti reticolari circolari. La risposta (spero!) È 257199853438240692.

Ecco il programma C:

#include "stdlib.h"
#include "stdio.h"
#include "math.h"
#include "string.h"

#define lim 1000000000L

char prime[lim];
long primes[50000000];
long len = 0;

int main(void)
{
    long i, j;
    for(i = 0; i < lim; i++)
    {
        prime[i] = 1;
    }

    for(i = 2; i < lim; i++)
    {
        if(prime[i])
        {
            for(j = 2*i; j < lim; j += i) prime[j] = 0;
            if((i-1)%4 == 0)
            {
                prime[i] = 2;
                //printf("%li\n", i);
                primes[len++] = i;
            }
        }

        if(i < 1000 || (i < 10000 && i%1000 == 0) || i%10000 == 0) printf("%li, %li\n", i, len);
    }

    printf("primes!\n");

    long a, b, c, v, total = 0, k;
    for(a = 0; a < len; a++)
    {
        v = primes[a]*primes[a]*primes[a];
        if(v > 50000000000L) break;

        for(b = 0; b < len; b++)
        {
            if(b == a) continue;

            v = primes[a]*primes[a]*primes[a]*primes[b]*primes[b];
            if(v > 50000000000L) break;

            for(c = 0; c < len; c++)
            {
                if(c == a) continue;
                if(c == b) continue;

                v = primes[a]*primes[a]*primes[a]*primes[b]*primes[b]*primes[c];
                if(v > 50000000000L) break;

                for(k = 1; k*v <= 50000000000L; k++)
                {
                    if(prime[k] == 2) continue;
                    total += k*v;
                }
            }
        }
    }

    for(a = 0; a < len; a++)
    {
        v = primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a];
        if(v > 50000000000L) break;

        for(b = 0; b < len; b++)
        {
            if(b == a) continue;

            v = primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[b]*primes[b]*primes[b];
            if(v > 50000000000L) break;

            for(k = 1; k*v <= 50000000000L; k++)
            {
                if(prime[k] == 2) continue;
                total += k*v;
            }
        }
    }

    for(a = 0; a < len; a++)
    {
        v = primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a];
        if(v > 50000000000L) break;

        for(b = 0; b < len; b++)
        {
            if(b == a) continue;

            v = primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[a]*primes[b]*primes[b];
            if(v > 50000000000L) break;

            for(k = 1; k*v <= 50000000000L; k++)
            {
                if(prime[k] == 2) continue;
                total += k*v;
            }
        }
    }

    printf("%li\n", 2*total);


    return 0;
}

Dobbiamo solo aggiungere i valori di n che hanno 420 punti reticolari circolari e sono nella forma 2k + 1! Tuttavia, sembra più difficile che per n = 2k e non riesco a vedere alcun metodo per questo. Sono anche un po 'incerto se la mia risposta anche a n sia corretta poiché il metodo è abbastanza contorto ... Qualcuno può confermarlo? Esiste un metodo accurato senza comportare un trattamento diverso n?

Sono completamente senza idee!

---

Sono principalmente interessato a come gestisco N = 2k + 1 da quando N = 2k posso fare come suggerisce John Feminella.

Answer 1

Suggerimento 1: il cerchio ha raggio n / & # 8730; 2, che non è mai un numero intero per il numero intero n, quindi A046080 non si applica mai.

Suggerimento 2: non preoccuparti di far scorrere il cerchio. Raccoglilo dalla carta millimetrata e pensaci, il quadrato che lo definisce e i punti di interesse ancora sconosciuti sulla circonferenza l'uno rispetto all'altro.

Suggerimento 3: l'angolo inscritto in un semicerchio è sempre di 90 gradi.

Suggerimento 4: in quanti modi un numero può essere scritto come la somma di due quadrati?

Suggerimento bonus da usare liberamente in tutto: simmetria!

---

AVVISO SPOILER!

---

Non leggere oltre finché non provi a risolverlo dai suggerimenti sopra

Se questi suggerimenti non sono sufficienti, ecco alcuni dei passaggi mancanti per interleave con i suggerimenti sopra:

Suggerimento 1.5: dovrai cambiare il tuo modo di vedere il problema poiché l'approccio che stavi usando si basa su una premessa errata.

Suggerimento 2.5: pensa a un punto reticolare sul lato sinistro dell'arco tra gli angoli superiori del quadrato. Per simmetria c'è un altro di questi punti direttamente alla sua destra e un terzo direttamente sotto. Cosa puoi dire della distanza tra questi punti e del trangle che formano?

Suggerimento 3.5: come puoi determinare quanti punti reticolari ci sono sul lato sinistro dell'arco tra gli angoli superiori del quadrato per ogni dato n?

Answer 2

Suggerimento n. 1. Il tuo lemma n. 2 non è del tutto corretto. Sei sicuro che sia questo il raggio?

Suggerimento n. 2. La risposta è strettamente correlata alla funzione somma dei quadrati, r (k, n). Ciò fornisce il numero di modi per rappresentare n usando k quadrati diversi, consentendo zeri e distinguendo tra ordine. Ad esempio, r (2, 5) è 8, perché ci sono 8 modi per rappresentare 5 usando 2 quadrati:

(-2)^2 + (-1)^2
(-2)^2 + 1^2
2^2    + (-1)^2
2^2    + 1^2
... (and the 4 additional expressions produced by reversing these 2 terms)

Puoi vedere che un cerchio di raggio p centrato sull'origine ha r (2, p ^ 2) punti reticolari. Ad esempio, un cerchio con raggio 5 ha:

(-4)^2 + (-3)^2
... and 7 others like this

5^2    + 0^2
(-5)^2 + 0^2
0^2    + 5^2
0^2    + (-5)^2

per un totale di 12. Quali tipi di numeri avrebbero 420 punti reticolari circolari? E se non fossero centrati sull'origine? Ti lascio prendere da qui.

Se vuoi un suggerimento molto più grande, ho marcito 13 ( http://rot13.com ) qualcosa che dovresti controllare qui:

uggc: //zngujbeyq.jbysenz.pbz/FpuvamryfGurberz.ugzy

Answer 3

Puoi fare riferimento a http://oeis.org/A046109/b046109.txt per controllare fino a 1000. Ho installato PARI / GP e ho usato uno degli script PARI qui: http://oeis.org/ A046109 per controllare i numeri più in alto.