Numeri - Discussioni

n003 Somma di cifre 6

Sn= 6 + 66 + 666 + 6666 +...+ (66...66)
dove l'ultimo termine, fra parentesi, e' composto di n cifre "6".

Quanto vale Sn ??

Paolo

Una curiosita'
ho notato che i primi 15 valori (oltre 15 Excel da valori approssimati) di Sn sono:

              6
             72
            738
           7404
          74070
         740736
        7407402
       74074068
      740740734
     7407407400
    74074074066
   740740740732
  7407407407398
 74074074074064
740740740740730

possiamo ottenere ciascuno di questi valori, scrivendo in sequenza le cifre 7,4,0 (n cifre per ciascun Sn)

              7
             74
            740
           7407
          74074
         740740
        7407407
       74074074
      740740740
     7407407407
    74074074074
   740740740740
  7407407407407
 74074074074074
740740740740740

e sottraendo da ciascun valore rispettivamente

1 2 2 3 4 4 5 6 6 7 8 8 9 10 10

Esiste una spiegazione?

Max

Sia an l'n-esimo termine della somma. Si ha:

an = 6*( (10^n-1)/9) = 2(10^n-1)/3 = 2*10^n/3 - 2/3

Sia ora 

bn = 2*10^n/3    e    cn=2/3,

per cui          an = bn - cn.

Essendo 

Sn = S(bn) - S(cn) 

basta applicare banali formule:

Sn = 2*( (10^(n+1) - 1)/9 )/3 - 2(n+1)/3

Roberto

Si puo' anche notare che per n <10 Sn e' 6*12345...., dove 12345... e' un numero di n cifre progressive.
Dopo il 10 (e fino a 19, poi non so) la storia cambia un po', ma e' facilmente memorizzabile.
Es per n=15 si ha:
Sn = 6 * 123456790123455
cioe' salta l'8 e raddoppia l'ultima cifra. Saluti

Intervento di ???
Gingillandomi un po' con questo vecchio
problema (è un paio di settimane che è
apparso) , ho notato alcune cose:

666666666666666...
 66666666666666...
  6666666666666...
   666666666666...
    66666666666...
     6666666666...
      666666666...
       66666666...
        6666666...
         666666...
          66666...
           6666...
            666...
             66...
              6...
740740740740740...

e non vi è motivo alcuno per il quale la serie di 740 non continui all'infinito.
Ma il problema poneva un quesito ben preciso : quale fosse la sommatoria per n definito.
Abbiamo tre possibilità:

n = 3a (cioè, 3, 6, 9, 12, etc.)
Sn = una stringa di 740 ripetuta "a" volte, da cui sottrarre 2a

n= 3a+1 (cioè, 1, 4, 7, 10, etc.)
Sn = una stringa di 740 ripetuta "a" volte, seguita da "7", da cui sottrarre 2a+1

n= 3a+2 (cioè, 2, 5, 8, 11, etc.) 
Sn = una stringa di 740 ripetuta "a" volte, seguita da "74", da cui sottrarre 2a+2

inizio thread

indice numeri

home

n009 Persistenza

Dario Uri

Ci sono due numeri di 3 cifre tali che appaiono le stesse 3 cifre alla destra di ogni loro potenza.
In simboli:

abc^k = ........abc
Dove abc rappresentano 3 cifre non necessariamente differenti.
Quali sono ?

Andrea Artesiani

E' equivalente a dire che:
abc^(k+h)-abc^k=...000 con h e k naturali qualunque

cioè abc^k(abc^h -1) mod 1000=0
per cui abc^k e abc^h -1 devono fornire i fattori 2^3 e 5^3 che formano il 1000.
Dovendo essere vero per ogni potenza di abc prendiamo le più piccole:

abc^2-abc

abc(abc-1) =2^3*5^3*...

abc e abc-1 sono uno e uno solo pari
=> abc mod 8=0 o abc-1 mod 8=0
inoltre dato che due consecutivi non possono essere entrambi multipli di 5 dev'essere:
abc mod 125=0 o abc-1 mod 125=0

cioè quattro possibilità:

1)abc mod 8=0 e abc mod 125=0
2)abc-1 mod 8=0 e abc-1 mod 125=0
3)abc mod 8=0 e abc-1 mod 125=0
4)abc-1 mod 8=0 e abc mod 125=0

caso 1 e 2: non vanno bene, perché abc sarebbe >=1000
caso 3: abc-1 può essere:
abc-1= 125, 250, 375, 500, 625, 750, 875
cui corrisponde:
abc = 126, 251, 376, 501, 626, 751, 876
e si vede che solo 376 è multiplo di 8 => abc=376
caso 4: abc può essere:
abc= 125, 250, 375, 500, 625, 750, 875
cui corrisponde:
abc-1= 124, 249, 374, 499, 624, 749, 874
e si vede che solo 624 è multiplo di 8 => abc=625

abbiamo quindi abc=376 o 625

Sturmtruppen

Uno è 625. Questo l'ho trovato immediatamente.
Anzi aggiungerei che (0625)^k= ...0625 ^___^
L'altro è 376. Trovato con l'aiuto del PC verificando quando
x=n^2-n, x-trunc(x) = 0. Per fortuna solo due sono stati selezionati.
Dopodichè ho verificato 376 per qualche potenza.

Sturmtruppen

Non ho avuto tempo di verificare con precisione ma da conti fatti mi risulta che non esiste un numero di QUATTRO cifre tale che
abcd^k= #...#abcd

Per cinque non ho nemmeno osato visto che avrei impegnato il PC per una mezzoretta. Ma quando ho tempo ci provo.

Silvio Sergio

> Non ho avuto tempo di verificare con precisione ma da conti fatti mi > risulta che non esiste un numero di QUATTRO cifre tale che
> abcd^k= #...#abcd

Basta controllare i quadrati. Dario ha voluto alzare un po' di polvere ;)

> Per cinque non ho nemmeno osato visto che avrei impegnato il PC per > una mezzoretta. Ma quando ho tempo ci provo.

Per n=1 tre valori: 1, 5, 6
Per n=2 ci sono due valori, 25 e 76
Per n=3 ancora due valori: 625 e 376

E' facile convincersi che passando da una dimensione alla successiva la parte finale si conserva, o meglio, se un numero axxx e` una soluzione per n, xxx lo e` per n-1. Quindi basta anteporre a ciascuno dei risultati di ordine n ognuna delle cifre possibili e controllare se il numero cosi` formato va bene per l'ordine n+1.
Ecco i risultati per n=10 (per gli n precedenti basta prendere le n cifre di destra). E` comunque facile arrivare anche a centinaia di cifre, volendo persino a mano.

18212890625, 81787109376

Paolo Licheri

Vedo che la soluzione e' stata gia' data, comunque, avendo fatto un lavoraccio, posto ugualmente i miei risultati.

Ne ho trovati 2+2
I primi due sono: 000 e 001
:-)
gli altri due: 376 e 625

con la forza brutta sarebbe stato fin troppo facile, allora ho voluto provare un altro metodo.

chiamero'
N = 100*a + 10*b +c il numero cercato;
X, X1, X2, ... numeri generici multipli di 1000,
Y, Y1, Y2, ... ecc. numeri generici multipli di 100

Alcune considerazioni preliminari:
se la condizione richiesta e' verificata per N^2, allora lo e' per qualsiasi N^k
infatti N^2 deve essere della forma
N^2 = X + N, quindi
N^3 = N^2 * N = X*N + N^2 = X*N + X + N = X*(N+1)*N
cioe'
N^3 = X1 + N e ancora della forma che verifica la condizione richiesta e, procedendo nello stesso modo, la verifica e' valida per qualunque esponente.

E' facile vedere che c puo' assumere solo i valori 0,1,5,6, unici numeri il cui quadrato termina con la stessa cifra

escludo immediatamente lo zero, infatti le potenze ab0^k, con k>2, sono della forma
...000, quindi dovrebbe essere N=000 (soluzione *anomala*)

provo per c=6

cerco quale puo' essere la penultima cifra b

N= 100*a + 10*b + 6
N^2 = 10000*a^2 + 100*b^2 + 36 + 200*a*b + 1200*a + 120*b
riunisco tutti i termini multipli di 100
N= Y1 + 10*b + 6
N^2 = Y2 + 20*b + 36

la differenza
N^2-N = Y3 + 10*b + 30 deve essere multipla di 100,, e tale deve essere anche la somma
10*b+30, quindi b+3 deve essere multiplo di 10, e b=7

cerco ora la terzultima cifra a

N=100*a + 76
N^2= 10000*a^2 + 15200*a + 5776

ossia
N = 100*a + 76
N^2 = X2 + 200*a + 776
e la differenza
N^2-N = X3 +100*a +700 deve essere multipla di 1000, quindi
a+7 multipla di 10, ed a=3
quindi N=376

con lo stesso procedimento, partendo da c=5, trovo N=625

invece, partendo da c=1, trovo l'altra soluzione anomala N=001

(ma che fatica, la prossima volta ritorno alla forza bruta :-)

inizio thread

indice numeri

home

n011 Codice cinese

Silvio Sergio

Devo trasmettere dei numeri usando un codice crittografico.
Ho deciso di codificare i numeri utilizzando quattro cifre che indicano i residui modulo 2,3,5,7 del numero da cifrare. Così 11 dintera` 1214 perche`
11 == 1 (mod 2)
11 == 2 (mod 3)
11 == 1 (mod 5)
11 == 4 (mod 7)

Voglio codificare senza ambiguita` i numeri da 1 a n. Quanto puo` valere al massimo n?
Che algoritmo suggerite per la decodifica?

Andrea Artesiani

> Voglio codificare senza ambiguita` i numeri da 1 a n. Quanto puo` valere a massimo n?

n non può superare 210, cioè 2*3*5*7.
Infatti 211=2*3*5*7+1 che ha quindi come codice 1111 che è lo stesso codice di 1. (in generale 210+x e x hanno lo stesso codice)

Paolo Licheri

> Che algoritmo suggerite per la decodifica?

In questo caso l'algoritmo piu' agevole potrebbe essere il metodo FB (forza bruta): una tabella con le 210 corrispondenze numero-codice da confrontare,
oppure un crivello, cioe':
se il primo valore del codice e'0 elimino tutti i dispari, se 1 i pari, poi, in base al secondo valore, elimino 2/3 dei numeri rimasti, poi ne elimino 4/5 e quindi 6/7.

Pero' ho voluto complicarmi la vita :-( per trovare una formula:

detto n il numero codificato e w,x,y,z le quattro cifre del codice, calcolo

p=7*RESTO(z-w;2)+z
q=5*RESTO(y-x;3)+y
dove p,q sono rispettivamente i resti di n/14 ed n/15

(notare che le espressioni <RESTO(z-w;2)> e simili seguono la sintassi di Excel, con il significato di resto della divisione (z-w)/2 ecc.)

quindi calcolo n con
n=14*RESTO(p-q;15)+p

volendo posso mettere tutto in un'unica espressione
n=14*RESTO((7*RESTO(z-w;2)+z)-(5*RESTO(y-x;3)+y);15)+(7*RESTO(z-w;2)+z)

notare che
_per n=210 le formule restituiscono 0; possiamo dire che vanno bene per i valori da 0 a 209, anziche' da 1 a 210
_le formule funzionano con i divisori 2,3,5,7; penso che con alcune modifiche si possa trovarne una piu' generale che funzioni con qualsiasi quaterna di divisori

Silvio Sergio

> _le formule funzionano con i divisori 2,3,5,7; penso che con alcune modifiche si possa trovarne una piu' generale che funzioni con qualsiasi quaterna di divisori

Il subject non e` casuale, i cinesi lo sanno fare con un qualsiasi numero di resti e con qualsiasi divisore, e da almeno 17 (!) secoli.

Nel nostro caso la formula cinese da:

n = RESTO(105w+70x+126y+120z;210)

Vediamo come si arriva a questi coefficienti.

Sia P=P1*P2*P3*P4=2*3*5*7=210
Chiamiamo Tj l'inverso di P/Pj nell'aritmetica modulo Pj, ovvero

T1*(3*5*7) == 1 (mod 2) => T1 = 1
T2*(2*5*7) == 1 (mod 3) => T2 = 1
T3*(2*3*7) == 1 (mod 5) => T3 = 3
T4*(2*3*5) == 1 (mod 7) => T4 = 4

Per calcolare l'inverso 1/a (mod p) basta calcolare a^(p-2)
perche` a*a^(p-2)=a^(p-1)==1 (mod p)

Quindi
T1 = 1/105 = 105^0 == 1^0 == 1 (mod 2)
T2 = 1/70 = 70^1 == 1^1 == 1 (mod 3)
T3 = 1/42 = 42^3 == 2^3 == 8 == 3 (mod 5)
T4 = 1/30 = 30^5 == 2^5 == 32 == 4 (mod 7)

Il teorema cinese dei resti afferma che, se

n == r1 (mod P1)
n == r2 (mod P2)
..
n == rm (mod Pm)

Allora n e` univocamente determinato a meno di multipli di P=P1*P2*..*Pm e vale

n = T1*(P/P1)*r1 + T2*(P/P2)*r2 + ... + Tm*(P/Pm)*rm (mod P)

nel nostro caso

n = 1*105*w + 1*70*x + 3*42*y + 4*30*z (mod 210)

inizio thread

indice numeri

home

n014 Palintipli
le discussioni nel NG relative ai tre temi proposti:

In quale piano abito? (palintipli)
......
Determinare un numero naturale che quadruplicato sia uguale al suo contrario.
Nella mia terminologia, il contrario del numero XYZ è ZYX;
scusate per il termine, ma non sapevo esprimermi meglio ( inverso e reciproco hanno altri significati )
PS: possibilmente non usate calcolatori...

Dario

Faccio un es. con 4 cifre:
ABCD*4=DCBA scomponendo
4000A+400B+40C+4D = 1000D+100C+10B+A
diventa
3999A+390B = 60C+996D

A < 3. Non puo' essere =1 perche' il primo termine sarebbe dispari mentre il secondo e' pari. Percio' A=2.
7998+390B = 60C+996D CeD devono essere cifre alte e B bassa. Con poche prove trovo:

2178*4 = 8712
Stessa cosa con 5 cifre 21978*4 = 87912.....

Massimo

Il numero naturale è 0 !!!!!!!

Pio

Io ho trovato casualmente 2178*4=8712

inizio thread

Rapporti allo specchio (palintipli)
Prendiamo una coppia formata da un numero e dal suo speculare (tipo 1234 e 4321) e facciamo il rapporto (gli zeri iniziali, e quindi anche quelli finali, non sono ammessi).
Ho scoperto che i possibili rapporti interi (oltre al banale 1 dei numeri palindromi) sono solo due, e danno origine a due gruppi di soluzioni. Quali sono e perche' non ce ne sono altri?
La forza bruta e' ammessa solo per trovare i due rapporti, poi bisogna lavorare...
P.S.
Non e' che ne abbiamo gia' parlato qualche tempo fa? le coppie che ho trovato mi ricordano qualcosa...

Paolo

Per il momento, il perche' non lo so.
Ho trovato, con la forza bruta, i due rapporti: 4 e 9, ed alcune caratteristiche interesanti
consideriamo il numero abcd, dove
a=qualsiasi valore tra 1 e 9
b=a-1
c=9-a
d=9-b

vale l'uguaglianza
abcd /dcba = a/d

1089 / 9801 = 0.111111 = 1/9
2178 / 8712 = 0.25 = 2/8
3267 / 7623 = 0.428571 = 3/7
4356 / 6534 = 0.666667 = 4/6
5445 / 5445 = 1 = 5/5
6534 / 4356 = 1.5 = 6/4
7623 / 3267 = 2.333333 = 7/3
8712 / 2178 = 4 = 8/2
9801 / 1089 = 9 = 9/1

gli stessi valori si trovano inserendo, tra le prime due e le ultime due cifre, un qualsiasi numero di cifre 9

989901/109989 = 9
8799912/2199978 = 4
ecc.

credo, ma non so dimostrarlo, che i numeri di questa forma siano i soli che hanno rapporto intero con il proprio speculare

Silvio

Ottimo. Io avevo trovato, con la classica brute force, le due famiglie
98[9]01 / 10[9]89 = 9
87[9]12 / 21[9]78 = 4
ed ero convinto che il nove si poteva inserire in molti rapporti senza alterare il risultato, come giustamente fai notare tu.
Per quanto rigurda l'unicita', ho fatto queste considerazioni:
sia r il rapporto a..z/z..a , sara' quindi z..a * r = a..z
1) se r>4 allora z=1, altrimenti non ci troviamo col numero di cifre. In questo caso a*r deve finire con 1. Basta un attimo per convincersi che l'unico caso possibile e' r=9, a=9, 9*9=81. Siamo arrivati a questo punto:
1..9 *
9 =
------
9..1

La seconda cifra deve essere 0 oppure 1, altrimenti ci sarebbe riporto Si vede facilmente che solo lo 0 va bene ed arriviamo a
10..9 *
9 =
-------
9..01
la penultima cifra moltiplicata per 9 deve terminare in 2 perche' con l'8 del riporto dell'81 deve dare 0, quindi deve essere 8
10..89 *
9 =
--------
98..01
E gia' avremmo finito, perche' il secondo riporto e' 8 e coincide col penultimo. Se pero' inseriamo un 9 vediamo che 9*9+8=89, ovvero ancora un 9 con riporto di 8. Quindi di 9 possiamo mettercene a piacimento. L'altro caso si trova in maniera analoga.

inizio thread

Palintipli
L'argomento e' stato in parte gia' trattato nel luglio 99 (e forse anche prima) nei thread "Rapporti allo specchio" e "In quale piano abito". Penso pero' che valga la pena di riprenderlo.
Chiamiamo *Palintiplo* (da palindromo e multiplo) un numero che sia multiplo del suo speculare (trascuriamo il caso banale dei veri numeri palindromi).
Indico con il simbolo [9] una stringa di n cifre 9,

Martin Beech (_The_mathematical_gazette_, Vol 74, #467, pp 50-51, March '90) ha osservato che 98[9]01 e 87[9]12 sono palintipli, ed ha espresso la congettura che siano gli unici esistenti.

(Nelle nostre discussioni eravamo arrivati allo stesso risultato)

Nell'archivio di rec.puzzles ho trovato articolo di Dan Hoey (Hoey@AIC.NRL.Navy.Mil) May, 1992, dove si dimostra che i numeri di Beech sono palintipli
(riporto la dimostrazione dopo uno spoiler, ma ricordo che anche Silvio, Dario ed io ... :-)
nota: la dimostrazione è riportata alla fine di questo thread

Inoltre Dan Hoey trova che ne esistono degli altri.
Quali?

Adriano

Non ho capito se ne esistono altri (?) oltre a quelli banali tipo:
indicando con [abcd] una stringa di n sottostringhe abcd

[8712]
e
[9801]

Paolo Licheri

E' un buon inizio. Comunque ne esistono altri, sempre derivati dai primi
due.

Adriano

Scusate la confusione in quanto segue, ma non ho trovato modo migliore per spiegarmi.

Con le convenzioni di prima e dividendo la costruzione dei numeri in parte iniziale, centrale e finale:

Parte iniziale:

[ 87 [9] 12 [0] ]

e

[ 98 [9] 01 [0] ]

Parte centrale:

[0]

Per costruire la seconda parte si ritorna a ritroso nelle scelte effettuate per la prima, riportando (es. per la prima serie di palintipli):
- 87 ogni volta che si e' messo 12,
- 12 ogni volta che si e' messo 87
- [9] ogni volta che si e' messo [9]
- [0] ogni volta che si e' messo [0]

Giusto? (Argh!)

Paolo Licheri

Giusto!

Direi che si puo' generalizzare in questo modo:

chiamiamo
P un qualsiasi palintliplo,
e, con le notazioni usuali,
[P] una stringa contenente n volte il palintlipo P

allora sara' palintlipo ciascun numero della forma
[p] [0] [p] [0]........[p]
dove non e' necessario che tutte le stringhe [p] o le stringhe [0] siano uguali tra loro, ma e' sufficiente che siano uguali due stringhe simmetriche (prima e ultima, seconda e penultima, ecc.), e ovviamente non si devono mescolare palintipli delle due famiglie 8712 e 9801,
esempio:
8712 000 87912 879999912 879999912 87912 000 8712
(notare che il numero e' della forma descritta, con alternanza di [p] e [0], se supponiamo, dove esistono due [p] consecutive, di separarle con una stringa di zero cifre zero)

Chiamerei un numero del genere pseudo_palindromo, infatti non e' palindromo se lo esaminiamo cifra per cifra, ma lo e' se consideriamo i diversi gruppi []
Per chiarire meglio la cosa, passando dai numeri alle lettere, consideriamo
le due parole:
ANNA e NANA
la prima e' un palindromo vero, la seconda uno pseudo_palindromo, considerando la divisione in sillabe.

Andrea Artesiani

Faccio notare una cosa che non mi sembra esplicita:
bisogna che i gruppi di [0] e [9] siano simmetricamente della stessa lunghezza:
es. 98 99 01 0 98 99 01
^^ ^ ^^
dove abbiamo inserito 99099.
un valore come:
98 99 01 0 98 9 01 non andrebbe bene.
^^ ^ ^
Analogamente per 8712.

Comunque aggiungo una piccola cosina:
Il problema è di determinare tutte le sequenze X di cifre che si possano inserire fra 9801 e 8712,
a partire da 9801, se chiamiamo X una sequenza di cifre che si possa
inserire fra 98 e 01, cioè tale che 98_X_01=9 * 10_Xsp_89
con Xsp =speculare di X

si dimostra che deve necessariamente essere:
8*(10^x -1)=9*Xsp -X dove x= numero di cifre di X

da cui si trova che:
X e Xsp sono multipli di 9;
X-Xsp è multiplo di 72
e X+Xsp termina con 8.

Potrebbe essere una cosa interessante...

inizio thread

(palintipli)
La dimostrazione di Dan Hoey (dall'archivio di rec.puzzles)

indichiamo con il simbolo [9] una stringa di n cifre 9,
e con [0] una stringa di n cifre 0

87[9]12 = 87[9]00 + 12 = (88[0]00 - 100) + 12 = 88[0]00 - 88
21[9]78 = 21[9]00 + 78 = (22[0]00 - 100) + 78 = 22[0]00 - 22

98[9]01 = 98[9]00 + 1 = (99[0]00 - 100) + 1 = 99[0]00 - 99
10[9]89 = 10[9]00 + 89 = (11[0]00 - 100) + 89 = 11[0]00 - 11

E' evidente che
4x(22[0]00 - 22) = 88[0]00 - 88
e che
9x(11[0]00 - 11) = 99[0]00 - 99.
QED.

inizio thread

indice numeri

home

n015 Permutazioni sincronizzate

Sistemare le 24 permutazioni delle cifre 1,2,3,4 incolonnate una sotto l'altra in modo che non ci siano 2 numeri uguali adiacenti verticalmente (uno sull'altro).
In generale per quali n, le n! permutazioni possono essere incolonnate in questo modo ?

Paolo Licheri

una possibile soluzione:

1234
2341
3412
4123

2314
3142
1423
4231

1324
3241
2413
4132

3421
4213
2134
1342

2431
1243
4312
3124

1432
4321
3214
2143

Considerazioni:
Ho diviso le 24 [n!] permutazioni in 6 [(n-1)!] gruppi di 4 [n] righe ciascuno, procedendo in questo modo:
_ La riga iniziale di ciascun gruppo e' formata dalla cifra 1 seguita da una delle possibili permutazioni di (234).Le sei righe iniziali saranno quindi: (1234)(1243)(1324)(1342)(1423)(1432)
_ In ciascun gruppo, ogni riga e' generata dalla precedente, spostando la prima cifra all'ultima posizione. Il primo gruppo e':
(1234)(2341)(3412)(4123)
e similmente gli altri.

Si nota che:
a)_Tutte le righe di ciascun gruppo sono tra loro *compatibili*, quindi all'interno del gruppo sono permesse tutte le possibili inversioni di righe. b)_Ogni riga di un gruppo e' *compatibile* con una ed una sola riga di ciascun altro gruppo; da cio' deriva che due gruppi possono essere saldati tra loro in quattro modi differenti.

A questo punto, partendo da un gruppo a scelta, aggiungo man mano gli altri gruppi, cercando, con pochi tentativi, le inversioni di riga necessarie.

> In generale per quali n, le n! permutazioni possono essere incolonnate in questo modo ?

Non ne sono del tutto sicuro, dovrei verificare se la proprieta' (b) e' valida per qualunque n.
Se cosi' fosse, il metodo dovrebbe funzionare comunque per n->infinito. Infatti basterebbe scrivere il primo gruppo, con le righe disposte in un ordine qualsiasi;
poi aggiungere via via gli altri gruppi, disponendo ogni volta come prima riga quella *compatibile* con l'ultima del gruppo precedente.

Paolo Licheri

> b)_Ogni riga di un gruppo e' *compatibile* con una ed una sola riga di
> ciascun altro gruppo; da cio' deriva che due gruppi possono essere saldati
> tra loro in quattro modi differenti.
...
> > In generale per quali n, le n! permutazioni possono essere incolonnate
> > in questo modo ?

> Non ne sono del tutto sicuro, dovrei verificare se la proprieta' (b) e'
> valida per qualunque n.

Ho fatto qualche verifica e la cosa non e' cosi' semplice.
Ho trovato:
_ per n pari (non ho la dimostrazione, ma per ora e' solo una congettura) sembra che presi comunque due gruppi, ciascuna stringa del primo risulti compatibile con ALMENO una stringa del secondo; in questo caso sarebbe comunque possibile agganciare i gruppi in successione

_per n dispari NO; per esempio non sono compatibili le stringhe appartenenti ai gruppi generati da [12345] ed [13524] (stringhe in cui le differenze tra due termini consecutivi sono costanti, a meno di 5)

Comunque la condizione che avevo ipotizzato era sufficiente, ma non necessaria, quindi non e' detto che con n dispari non sia possibile. La cosa richiede ulteriori approfondimenti.

Andrea Viscovich

Anche se in ritardo, ma l'ho letto solo ieri, ecco la mia soluzione.
Chiamo permutazione semplice di una combinazione una qualunque combinazione che si ottiene dalla originale spostando i suoi termini ciclicamente ossia senza scambi di posizioni.
Parto da un esempio con 5 elementi.
Come gia' fatto notare da Paolo, tutti gli elementi appartenenti ad una permutazione semplice sono tra di loro compatibili.
12345
51234
45123
34512
23451
Quindi possiamo considerare solo la prima riga, che chiamiamo generatrice, ce ne sono 24 nel coso di n=5.
Ora dobbiamo vedere quante di queste generatrici sono tra di loro incompatibili.
Ce ne sono 6 gruppi disgiunti, 4 alla volta incompatibili fra di loro, per cui
per n=5 soluzione esiste (e non poche), in quanto basta fare in modo che 2 generatrici incompatibili tra loro non siano in ordine ma
intervallate.
Per vedere questo vediamo di costruire una funzione stato che ci restituisca un valore uguale per tutte le permutazioni.
Lo stato sara' costituito da 3 cifre in questo modo. La prima indica la distanza della cifra 1 dalla cifra 2 della combinazione. La seconda la distanza di 2 da 3. La terza la distanza di 3 da 4. Non serve altro.
La combinazione
12345 = 111
13254 = 243
e cosi' via.
In questo modo abbiamo proprio 24 combinazioni, in quanto al primo posto posso avere 4 numeri al secondo 3 e al terzo 2.
Infatti consideriamo la combinazione 1xy (ossia 12zzz), x non puo' valere 4, e y non puo' valere ne 3 ne 5-x in quanto posizioni gia' occupate. Si puo' vedere che il gruppo 111 e' incompatibile con le generatrici
222
333 che e' proprio l'esempio fatto da Paolo = 13524
444

Cio' che segue dovrebbe valere per n dispari e primo. Non cambia la conclusione finale.
In generale presa una generatrice a caso, xyz essa è incompatibile con kx mod n ky mod n kz mod n per ogni k tra 1 e n-1.
Esempio
124 incompatibile con
243 in questo caso k = 2 (2=2*1,4=2*2,3=4*2 mod 5)

In generale quindi per ogni n si hanno (n-1)! generatrici raggruppabili in gruppi di n-1 elementi incompatibili tra di loro.
Per cui soluzione esiste sempre.
Almeno secondo me e quanti riesco a convincere con questa dimostrazione :-)

indice numeri

home

n018 Primi e Fibonacci

Silvio Sergio

Considera la normale sequenza di Fibonacci 1,1,2,3,5,8,13,21,..
E' vero che ogni numero primo divide almeno un termine della successione? Per esempio 7 divide 21, l'ottavo numero di Fibonacci.

Paolo Licheri

Non ho la dimostrazione, ma solo una constatazione:
per ogni numero primo p, si trova un multiplo entro i primi p+1 termini della sequenza di Fibonacci

per esempio
p=7 e' divisore di F_8=21
p=23 e' divisore di F_24=46368
p=11 e' divisore di F_10=55

Maurizio Codogno

Un ragazzo intelligente potrebbe usare quello che hai scritto come un ottimo aiutino.

Crios

> Considera la normale sequenza di Fibonacci 1,1,2,3,5,8,13,21,..
> E' vero che ogni numero primo divide almeno un termine della successione?
> Per esempio 7 divide 21, l'ottavo numero di fibonacci.

Non solo, a me sembra che se p e' primo, p divida sempre F_(p+1) exor F_(p-1) :

11 : F_10 =3D 55 =3D 11*5
13 : F_14 =3D 377 =3D 13*29
17 : F_18 =3D 2584 =3D 17*19*2*2*2
19 : idem
23 : F_24 =3D46368 =3D 23*7*3*3*2*2*2
=2E..

Silvio Sergio

> Non solo, a me sembra che se p è primo, p divida sempre F_(p+1) exor F_(p-1) :

Anche Paolo l'ha notato, e Maurizio dice che e' un bell'aiuto per la dimostrazione. Ma gia' l'avevo visto su rec.puzzles, dove ho preso il problema, senza capirci nulla. A me pare che anche li' si faccia una semplice constatazione.

Set F_1 = 1, F_2 = 1, F_3 = 2 etc. Then a prime p which ends in 1 or 9 will divide F_n if (p-1) divides n, and a prime p ending in 3 or 7 will divide F_n if (p+1) divides n. Here F_7 divides 8. This leaves the cases p = 2 and 5, but they are easily dealt with :-)

Che ne dite?

Maurizio Codogno

: Anche Paolo l'ha notato, e Maurizio dice che e' un bell'aiuto per la : dimostrazione.

In realta` non lo e`, anche se lo pensavo.
O forse lo e`, ma non sono riuscito a trovare una dimostrazione bella.

Comunque e` abbastanza facile dimostrare che per ogni k c'e` un numero di fibonacci che e` divisibile per k.

Consideriamo la successione dei valori modulo k. E` ovvio che il numero di distinte coppie successive di valori e` finito, essendo al piu` k^2 . Quindi avremo due numeri distinti m e n tali che
F_m == F_n (mod k) e F_(m+1) == F_(n+1) (mod k)
ma questo significa che anche F_(m-1) == F_(n-1) (mod k) e via tornando indietro fino a che avremo F_1 == F_l (mod k) e F_2 == F_(l+1) (mod k) da cui F_(l-1) == 0 (mod k), qed.

Notare che non ho usato l'ipotesi k primo, ma d'altronde non ho dimostrato il teorema forte (ad esempio, se non erro il primo n per cui F_n == 0 (mod 10) e` 15)

Crios

Notare che non ho usato l'ipotesi k primo, ma d'altronde non ho dimostrato il teorema forte (ad esempio, se non erro il primo n per cui F_n == 0 (mod 10) e` 15)

Non erri : F_15=610
Ma mi pare di aver visto un errore fatale...
La butto giu', se sbaglio mi cospargero' il capo di cenere :
hai solo dimostrato che F(l-1) == 1 (mod k),
ma questo si ottiene entro k-1 (?)
infatti F_8 = 21

Maurizio Codogno

: Ma mi pare di aver visto un errore fatale...

Infatti ho detto che ho dimostrato *un altro risultato*, piu` debole in un senso (non trovo un resto zero nei primi k+1 fib, ma nei k^2) e piu` forte in un altro ( k non deve essere primo)

Crios

> Infatti ho detto che ho dimostrato *un altro risultato*, piu` debole in un senso (non trovo un resto zero nei primi k+1 fib, ma nei k^2) e piu` forte in un altro ( k non deve essere primo)

Hai perfettamente ragione. Avevo fretta ed ho detto due castronerie. Spero di farmi perdonare dimostrando la tua congettura originale, usando la primalita' :

----------------------------------------------

Sia E_n una successione che soddisfa alla proprieta'
E_(n+2)=3DE_(n+1) + E_n (in realta' basta molto meno)
Def. dato un k una sottosequenza di E_n (E_a, .. ,E_b)=3D(0, .. ,0), si dice k-fondamentale (k-f) se E_a=3DE_b=3D0 (mod p)
e per ogni a<=3Dx<=3Db F_x<>0 (mod p)
Ad esempio (0,0) e (0,1,1,2,3,0) sono sequenze 5-f,
lunghe rispettivamente 1 e 5 (...)

Lemma (i), Se p primo, esistono (p-1) sequenze p-f distinte
e di ugual lunghezza, diverse da (0,0) :
Una SPF esiste (..., stesso arg. di Codogno), moltiplicandola per m=3D1..(p-1) si ottengono tutte. Infatti se x=3DE_a+1 (mod p), qualsiasi altro y=3D(E')_a+1 (mod p) di un'altra sequenza p-f si puo' ridurre a m*x (mod p) se m=3Dy*(x^-1) (il reciproco e' ben definito su PK sse x><0=

e p primo), e questo basta per metterla in corrispondenza.QED

Lemma (ii), una sequenza p-f, con p primo, =E8 lunga al massimo p+1 Sia l la lunghezza di una p-f, l e' anche il numero di coppie successive (distinte) di valori che questa presenta. Notiamo che due p-f hanno tutte coppie distinte (...). In totale le coppie sono p^2-1 (tolta la coppia banale (0,0)) e esistono (distinte da (0,0)) esattamente p-1 sequenze p-f

per il lemma (i), quindi ipotizzando che queste occupino
tutte le coppie possibili l_max=3D(p^2-1)/(p-1)=3Dp+1.QED

vale quindi
Th. Per ogni p primo, p divide almeno un F_n per n<=3Dp+1
Infatti dato p primo esiste una sequenza p-fondamentale che =E8 lunga al massimo p+1 (ii), laddove F_b=3D0 (mod p), cioe' p|F_b.

E' anche immediato dimostrare che preso quel b tale che p|F_b,
si ha anche p|F_(k*b) per ogni k (una sequenza p-f finisce sempre con un'altra seq. p-f), e quindi anche che F_b|F_(k*b), che e' un risultato classico.

Ufff... che lunga che e' venuta...

Vinny

Ho sentito solo parlare di questa "sequenza fibonacci"....ma cos'è?

Silvio Sergio

La succesione di Fibonacci comincia due 1 ed ogni termine successivo e' la somma dei due precedenti.
1, 1, 2(1+1), 3(1+2), 5(2+3), 8 ecc.

Vinny

Ho capito perfettamente, grazie!
Ma ora ti (vi) chiedo: che particolarità ha questa serie? A che vantaggi porta? Chi la conosce a cosa gli potrebbe servire?
così a naso non mi sembra ninete di particolare...potrei inventare serie infinite in quel modo:
1,2,3,6,11,20,27,.... giusto?

MaxArt

> 1,2,3,6,11,20,27,.... giusto?

Sbagliato, l'ultimo numero dovrebbe essere 37 :-)

Cmq sì... puoi divertirti a scrivere formule ancora più generali... Ma su Fibonacci è stato scritto così tanto... ma così tanto...

Poi è incredibile come i numeri di Fibonacci si ritrovino... nella natura!!! Prendi ad esempio un girasole: la parte centrale è formata da spirali logaritmiche che si incrociano, andando alcune in un verso, altre nell'altro.
Il numero di spirali logaritmiche che vanno in un verso è un numero della sequenza di Fibonacci, e il numero di quelle che vanno nell'altro è il numero di Fibonacci successivo!!!
Sconcertante, eh?

E se fai caso, anche le foglie di un fiore sono messe in modo tale da formare angoli tra loro che dividono l'angolo giro in un numero che è pari ad uno della successione di Fibonacci... non so se sono stato chiaro.

Inoltre: il limite del rapporto tra due termini consecutivi della successione di Fibonacci tende alla proporzione divina (o sezione aurea: (1 + sqrt(5))/2 = 1.618...), un numero abbondantemente usato (ed abusato... basti pensare al nome per immaginare le interpretazioni che ha avuto nei secoli) in passato nelle arti figurative.
Questa è una caratteristica però di tutte le successioni in cui ogni termine è la somma dei due precedenti, come anche la successione di Lucas (generata da 1 e 3).

La proporzione divina è soluzione dell'equazione x^2 = x + 1. Infatti, se fai il quadrato di 1.618... ottieni 2.618... E adesso prova a fare l'inverso
:-)
Sì, ottieni 0.618... (e credo che a volte si intenda questo numero come sezione aurea...). La proporzione divina si indica in genere con la lettera greca "phi" minuscola.

Ora ti insegno un giochetto: prendi un foglio di carta in cui il rapporto tra larghezza e altezza sia pari alla proporzione divina. Mettilo con lato più lungo alla base e da sinistra disegna un quadrato di lato pari all'altezza. Il pezzo rimanente avrà ancora il lato più lungo in proporzione divina col lato più corto! Nel pezzo rimanente, disegna dal basso un quadrato... poi lo stacchi da destra... poi dall'alto... poi di nuovo da sinistra e così via. Prova poi a congiungere gli estremi delle linee che hai tracciato con una linea curva: otterrai una spirale logaritmica :-) Che ti avevo detto dei girasoli poco fa? :-)

Maurizio Codogno

: Sbagliato, l'ultimo numero dovrebbe essere 37 :-)

35, vorrai dire!

MaxArt

> : Sbagliato, l'ultimo numero dovrebbe essere 37 :-)
> 35, vorrai dire!
No, 37! La somma dei tre numeri precedenti: 6 + 11 + 20 = 37.

Maurizio Codogno

: > : Sbagliato, l'ultimo numero dovrebbe essere 37 :-)
: > 35, vorrai dire!
: No, 37! La somma dei tre numeri precedenti: 6 + 11 + 20 = 37.

E perche` la somma deve essere quella dei tre numeri precedenti? La *mia* serie continua con ... 35, 60, 101, 168 ...

indice numeri

home

n019 Numero bilanciato

Dario

In base 10 i numeri 5,17,235,1234567890... sono tutti CD, perche' sono composti da Cifre Differenti.
Conseguentemente chiameremo CR i numeri 11,1234561,4458933,999999... perche' contengono Cifre Ripetute.
Definiamo Numero Bilanciato (NB) un intero n tale, che fra tutti gli interi da 1 a n-1, esattamente la meta' sono CD.
Trova l'unico NB esistente.

Stefano

NB=11221

almeno credo

Dario

Credi bene, ottimo!

Paolo

Al momento di spedire questo post, vedo che la risposta e' stata gia' data da Stefano.
Riporto comunque il ragionamento che ho fatto per trovare NB=11221.

Nell'insieme dei numeri di n cifre, complessivamente 9*10^(n-1), si possono agevolmente contare i CD.
Infatti la prima cifra da sinistra puo' essere scelta in 9 modi (qualsiasi cifra eccetto lo 0);
la seconda cifra ancora in 9 modi (qualsiasi cifra eccetto quella gia' scelta);
la terza in 8 modi (escludendo le due cifre scelte in precedenza), e cosi via.
In sostanza i CD di n cifre (con n<=10) sono
9*9!/(10-n)!

Allora posso analizzare i primi 9999 numeri

cifre n CD CR

1 9 9 0
2 90 81 9
3 900 648 252
4 9000 4536 4464
________________________
tot 9999 5274 4725

Aggiungo ora altri 1000 numeri, da 10000 a 10999

sono tutti della forma 10xxx, quindi per il conteggio dei CD, la prima x puo' essere scelta in 8 modi, la seconda in 7, la terza in 6; ci saranno quindi 8*7*6=336 CD

In totale, tra i primi 10999 numeri, ci sono 5610 CD e 5389 CR, con una differenza di 221 a favore dei CD.
Basta allora aggiungere 221 numeri, da 11000 a 11220, tutti CR per via delle due cifre 1 iniziali.

indice numeri

home

n020 Serie geometrica

Dario

Qual e' il prodotto dei primi 10 termini di una serie geometrica dove il primo termine e' 1 ed il decimo termine e' 2 ?

Bianchin

Dario

> 32

E' vero. Pero' devi postare il ragionamento.

Bianchin

a^0 = 1
il decimo termine è a^9 = 2

faccio la radice nona di 2 che è a

e quindi faccio

a^((0+1+2+3+4+5+6+7+8+9) / 9) = a^(45 / 9) = a ^ 5 = 32

> a^((0+1+2+3+4+5+6+7+8+9) / 9) = a^(45 / 9) = a ^ 5 = 32

MaxArt

Errore :o)
Attento...
Sarebbe a^(0+1+...+9), non come hai scritto tu...
a^5 è 2^(5/9)

Bianchin

Cazzarola hai ragione... eheh

a^(0+1+2+3+4+5+6+7+8+9) = 2^((0+1+2+3+4+5+6+7+8+9) / 9) = 2^(45 / 9) = 2 ^ 5 = 32

avevo fatto il ragionamento a mente e quando mi è stata chiesta la dimostrazione l'ho scritta velocemente senza controllare eccessiavente. Starò più attento in futuro... ;-)

Fabio

Allora:
chiamo "a" la ragione della serie geometrica
I 10 termini sono:
1
1*a
1*a*a = a^2
a^3
.
.
.
a^9 = 2

Il prodotto di questi termini e' 1*a*a^2*...a^9, cioe' a^(1+2+...+9) = a^45 = (a^9)^5 = 2^5.Ciao, Fabio