Newsgroup: it.hobby.enigmi
Titolo: Un cerchio

Qual e' il cerchio piu' piccolo che passa per 12 punti a coordinate intere?
Ciao!!!  ((^__^))
livio

 intere?
:-P
ma non son sicuro
questo è il più ovvio, e pertanto è sbagliato
-
spoiler
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
--
centrato nell'origine e raggio 5?
temo ce ne siano di più piccoli, basta cambiare il centro. 

 centrato nell'origine e raggio 5?
La risposta e' dentro di te... ma e' sbajata!!!  :o)))
Ciao!!!  ((^__^))
Livio


Spoiler
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
E' il cerchio di raggio = sqr(0.5^2+3.5^2)
Ciao ciao
*frankyz


E quindi anche:
Spoiler
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
V
E' il cerchio di raggio = sqr(2*2.5^2)
Ciao ciao
*frankyz

 ha scritto:

Credo proprio che sia quello!
Che ne dite, proviamo a generalizzare? Cioe':
Qual e' il cerchio piu' piccolo che passa per N punti
a coordinate intere?
Di questo ignoro la risposta. (Cosi' gioco anch'io)
Ciao!!!  ((^__^))
Livio

 Di questo ignoro la risposta. (Cosi' gioco anch'io)
Forse e' meglio, per simmetria:
"Qual e' il cerchio piu' piccolo che passa per 4*N punti
a coordinate intere?"
N    Raggio
1    SQR(2)/2
2    SQR(10)/2
3    SQR(50)/2
4    SQR(130)/2
5    SQR(1250)/2
...
Saranno giusti?  Qualcuno vuol continuare?
E' un caso che i termini >2 siano multipli di 10?
0,2,10,50,130,1250,... potrebbe essere una nuova sequenza
da inserire sulla  On-Line Encyclopedia of Integer Sequences
anche se qualche cosa mi dice che non sara' monotonica...
Pero' ha l'aria infinita. Usando terne pitagoriche ho trovato
cerchi con centinaia di punti a coordinate intere.
Bah!  Se son rose...
Ciao!!!  ((^__^))
Livio

 E' un caso che i termini >2 siano multipli di 10?
Per N=6     R=SQR(650)/2
Anche questo e' multiplo di 10.
Che c'azzeccano questi cerchi col fatto che noi abbiamo
dieci dita?
Ciao!!!  ((^__^))
Livio

 Per N=6     R=SQR(650)/2
La sequenza (con una semplice modifica) compare nella
On-Line Encyclopedia of Integer Sequences
guardate qui:
http://tinyurl.com/5wn2e
in particolare notare quanto e' grosso il
caso per N=11 rispetto a N=10 e N=12...
ciao,
g.

On-Line Encyclopedia of Integer Sequences
Ciao Giovanni.
A prima vista mi sembra che la sequenza da te suggerita non sia
quella chiesta da Livio, nonostante sia una parente MOLTO vicina.
Infatti e' definita come sequenza degli "Smallest k such that
circle x^2 + y^2 = k passes through exactly 4n integer points".
Questa sequenza pone il vincolo che i cerchi abbiano centro
nell'origine, mentre Livio non ha messo questo vincolo.
Livio ottiene cerchi piu' piccoli di quelli descritti dalla
sequenza, come gia' si vede dal caso n=1 che porta un raggio 1
nella sequenza, ma un raggio sqr(2)/2 nell'accezione di Livio.
Se riusciamo a trovare altri termini, almeno fino ad n=23, potremmo
in effetti proporre la sequenza al maintainer di OEIS e collegarla
a quella da te segnalata.
Ciao,
       Antonio

 ha scritto nel messaggio
news:f7r5l0lvfdcmda042...@4ax.com...

qualcuno potrebbe spiegare il procedimento utilizzato per arrivare alla
soluzione?

E' un caso che i termini >2 siano multipli di 10?
Forse no, chissa'? Cercando soluzioni solo tra i multipli
di 10 ho potuto trovare anche:
 n  raggio
--  ------------------
27  sqr(2442050)/2 [*]
30  sqr(3591250)/2 [*]
32  sqr(1602250)/2 [*]
36  sqr(4165850)/2 [*]
(ho messo l'asterisco, cosi' ci ricordiamo di verificare che
 siano cerchi di raggio minimo per i relativi n... ;-)
Ci sentiamo per eventuali aggiornamenti.
Ciao,
       Antonio

 dieci dita?
La butto lì: diciamo che abbiamo DUE mani, ciascuna con CINQUE dita.
sqrt(2)*sqrt(5) mi sembrano due valori più significativi.
Il primo potrebbe dipendere dal fatto che la figura ha simmetria 
*quadrata*,
il secondo, mi ricorda qualcosa,... che non sia in riferimento al 
rapporto aureo?
boh!
ciao
paolo 

 nell'origine, mentre Livio non ha messo questo vincolo.
Anche se... rileggendo la loro definizione non sembra che sia
posto questo vincolo, neppure sottintendendo k intero. Pero'
puo' essere una conseguenza, da verificare, dell'aver posto
k intero.
Piuttosto mi piace quel "exactly" che toglie di impiccio sul
fatto che la sequenza non e' sempre crescente. Allora si
potrebbe riprovare anche quella con n al posto di 4N:
n    Raggio
2    1/2
3    5/4    (!)
4    sqr(2)/2
5    ?
Ci sara' pure un cerchio che passa per cinque punti interi
soltanto, o no? (ma non mi sembra banale)
Ciao!!!  ((^__^))
Livio

 arrivare alla soluzione?
Bruteforce. Non penso che ci sia molto altro.
Ciao!!!  ((^__^))
Livio


La sequenza "cugina" che ho segnalato coincide con quella trovata
con la brute force in tutti i punti (da un punto di vista ideale).
Essa e'
1,5,25,65,625,325,15625,1105,4225,8125,9765625,5525,
244140625,203125,105625,27625,152587890625,71825,
3814697265625,138125,2640625,126953125,2384185791015625,160225
ed e' pensata per i cerchi passanti dall'origine.
(x^2+y^2=k)
Apparentemente tutte le soluzioni che avete trovato
si ottengono da quelle sopra spostando il centro in,
per esempio, (1/2, 1/2) e riducendo il raggio di un fattore
sqrt(2).
Da una soluzione di una classe si ottiene subito una soluzione
dell'altra.
Questo naturalmente non esclude che si possa fare qualcosa di
diverso ponendo il centro in un punto ancora diverso.
Per determinare in quanti modi diversi un numero N puo' essere
espresso come somma di 2 quadrati interi si puo' usare
la fattorizzazione di N.
Il metodo e' spiegato ad esempio qui
http://mathworld.wolfram.com/SumofSquaresFunction.html
dal metodo si capisce anche perche' c'e' questa predominanza
del fattore 5 (e' il numero primo piu' piccolo
della forma 4k+1...) e perche' i numeri primi siano
piu' bastardi.
Sapendo il metodo, si puo' rovesciare e usare per
generare velocemente numeri che abbiano esattamente un
certo numero di rappresentazioni come somma di quadrati.
Con questo non voglio dire (bisognerebbe pensarci un po'
di piu') che questo risponda automaticamente al problema
di Livio, ma questo sistema fornisce velocemente
delle buone soluzioni (al momento coincidenti con tutte
quelle che avete trovato)
Non mi e' chiaro in che modo state verificando i raggi minimi per
cerchi non centrati in 0,0 o (1/2,1/2).
Ciao,
g.


Ciao, e' stato trovato da Andre' Schinzel (1958) che esiste sempre un
cerchio
che passa per n punti interi e piu' precisamente:
se n=2*k   il cerchio di centro (1/2, 0) e raggio (1/2)*5^((k-1)/2)
se n=2*k+1 il cerchio di centro (1/3, 0) e raggio (1/3)*5^k
Cercando Schinzel's theorem su google si trovano tanti riferimenti.
ciao!

k intero.
Il vincolo non si vede direttamente dal testo, ma dall'equazione
x^2 + y^2 = k  confrontata con l'equazione di una circonferenza
generica:  (x - x_c)^2 + (y - y_c)^2 = r^2, in cui (x_c, y_c)
sono le coordinate del centro.
Ad esempio l'equazione piu' semplice che descrive la tua
sequenza dei cerchi minimi assoluti e'
(x - 1/2)^2 + (y - 1/2)^ = r^2
che ho usato nel mio programma. 
Detto questo, ho pero' fatto una scoperta molto interessante.
Avendo calcolato ieri notte altri elementi della sequenza ho
potuto fare un confronto tra la nostra sequenza e quella dei
cerchi vincolati ad avere centro nell'origine, e mi sono accorto
di questo: le due sequenze sono *identiche* a meno di un fattore 2.
Questo fatto mi ha molto sorpreso!
Infatti se pensiamo al cerchio minimo che passa per 4 punti a
coordinate intere, la nostra sequenza intercetta il pattern
.**
.**   cioe' p. es. i punti (0,0) (0,1) (1,1) (1,0), vertici
...   di un quadrato di lato 1 parallelo agli assi
mentre quella dei cerchi con centro nell'origine intercetta
.*.
*.*   cioe' i punti (0,1) (1,0) (-1,0) (0,-1), vertici di
.*.   un quadrato di lato sqr(2) inclinato di 45 gradi
e non pensavo che potessero essere messi in relazione per ogni
valore di n.
Poi mi sono dato una spiegazione: il pattern dei 4n punti
intercettati e' necessariamente simmetrico, e quindi tutte
le circonferenze che intercettano pattern di quel tipo devono
essere simili, cioe' devono coincidere a meno di una rotazione,
una traslazione e un cambiamento di scala.
Nel nostro caso per ottenere i cerchi minimi assoluti a partire
da quelli vincolati ad avere centro nell'origine, basta fare una
traslazione da (0,0) a (1/2,1/2), una rotazione di 45 gradi e
una riduzione di scala di un fattore sqr(2).
Questa trasformazione e' identica per ogni valore di n.
Non troppo intuitivo, eh?  ;-)
Ciao,
        Antonio

 per cerchi non centrati in 0,0 o (1/2,1/2).
Io non l'ho fatto per nulla. Avevo solo verificato che le sol
per (1/2,1/2) fossero a raggio minore di quelle per (0,0),
senza accorgermi del costante rapporto sqr(2).
Ma guarda te, se uno che si mette a far puntini su un
foglio quadrettato deve trovarsi in 'sto casino...  :o)))
Ciao!!!  ((^__^))
Livio

per cerchi non centrati in 0,0 o (1/2,1/2).
Ahem, non so Livio, ma io *NON* sto facendo questa verifica!  :-]
Io sono andato avanti cosi': ho iniziato con un foglio di carta
a quadretti a cercare a mano i raggi minimi per piccoli valori
di n, e mi sono accorto che erano tutti centrati in (1/2,1/2) e
avevano raggio della forma sqr(k)/2. Quindi ho ipotizzato che
questa regola si mantenesse anche al crescere di n e ho scritto
un programma basato su questa ipotesi. Non molto scientifico,
mi rendo conto, pero' sembra aver funzionato...  ;-)
Comunque, come dicevo nell'altro messaggio, la simmetria del
pattern dei 4n punti intercettati mi sembra che possa portare
ad escludere (geometricamente) l'esistenza di cerchi piu'
piccoli di quelli centrati in (1/2,1/2). Che ne pensi?
Saluti,
         Antonio

foglio quadrettato deve trovarsi in 'sto casino...  :o)))
Allora non sono l'unico!  :-)))
Saluti,
         Antonio

 Cercando Schinzel's theorem su google si trovano tanti riferimenti.
Interessante!
Dunque il nostro cerchio N=5 potrebbe essere quello con
coordinate (-8,0)(-2,8)(7,5)(7,-5)(-2,-8) e centro (1/3,0)
Ma sara' il minimo? Schinzel non lo assicura.
Per n=4 e n=8 fornisce palesemente cerchi non minimi.
Per cercare un N=5 minore ora pero' conosciamo il campo
di ricerca e il lavoro non dovrebbe essere pesantissimo,
per trovare il minimo o dimostrare che quello gia' lo e'.
Chissa' che ruotandolo di 37° e spostando l'origine di
1/7 e dividendo tutto per il rapporto aureo...  :o)))
Ciao!!!  ((^__^))
Livio

 Ma sara' il minimo? Schinzel non lo assicura.
Sicuramente non e' il minimo, ho trovato questo:
(x-r)^2+y^2 = r^2 con r=25/4.
Dovrebbe passare solo per
(0,0)(10,5)(10,-5)(8,6)(8,-6).
Della stessa forma ce ne e' uno con raggio r=125/4 passante solo per 7
punti.
Magari funziona sempre con raggi 5^k/4 quando n=2*k+1.
Io col computer non sono capace a verificarlo :-(
ciao

solo per 7 punti.
Cercando in rete materiale sull'argomento, mi sono imbattuto in
questo sito che nel maggio 2002 proponeva il problema a 7 punti:
http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/challenges/May2002.html
nella soluzione si dice che il cerchio di raggio minimo per 7 punti
e' quello con centro in (5/22,9/22) e raggio sqr(276250)/22 (non ho
verificato ma la fonte mi sembra attendibile ;)
A questo punto brancolo nel buio rispetto alla ricerca di un metodo
valido per ogni n!
Ciao,
       Antonio

 (0,0)(10,5)(10,-5)(8,6)(8,-6).
Io avrei trovato questo che dovrebbe essere il piu' piccolo
cerchio passante esattamente per soli 5 punti interi:
r = 25/3/sqr(2)
Centro = (31/6, 17/6)
Punti: (0,0) (1,-7) (6,3) (8,-8) (11,-2)
Qualcuno conferma/confuta?
Ciao!!!  ((^__^))
Livio