Come continua la sequenza: 742, ...

[panurgo]

Arpionato dal blog di Tanya Khovanova: $742 = 247\cdot3+1$

[Quelo]

$\displaystyle 742+\sum_{k=1}^n 742\cdot10^{4k}+5\cdot10^{4k-1}$

$\displaystyle \frac{[742+\sum_{k=1}^n 742\cdot10^{4k}+5\cdot10^{4k-1}]-1}{3}=\frac{741}{3}+\sum_{k=1}^n \frac{742\cdot10^{4k}}{3}+\frac{5\cdot10^{4k-1}}{3}=247+\sum_{k=1}^n 247\cdot10^{4k}+\frac{10^{4k}}{3}+5\cdot10^{4k-1}-\frac{10\cdot10^{4k-1}}{3}=247+\sum_{k=1}^n 247\cdot10^{4k}+5\cdot10^{4k-1}$

[Bruno]

Bravo, Sergio

La tua proposta non esclude che vi siano altri tipi di termini, a prima vista, ma è un ottimo risultato.

[Quelo]

Testando tutti i numeri fino a $10^7$ se ne trovano solo 2 con la propietà richiesta: 742 e 7425742 da cui si deduce la formulazione generale.
Possiamo dimostrare che non ci sono numeri di 2 cifre

$\displaystyle 10a+b=3(10b+a)+1;\quad 7a=29b+1;\quad a=\frac{29b+1}{7}$ che non ha soluzioni intere per $1\le b\le3$

Allo stesso modo possiamo dimostrare che per numeri di 3 cifre esiste una sola soluzione

$\displaystyle 100a+10b+c=3(100c+10b+a)+1;\quad 20b=97a-299c+1;\quad b=\frac{97a-299c-1}{20}$
$\displaystyle c=1 \;\Rightarrow\; 3\le a\le5;\quad b=\frac{97a-300}{20}$ non ha soluzioni intere
$\displaystyle c=2 \;\Rightarrow\; 6\le a\le8;\quad b=\frac{97a-599}{20}$ ha soluzione solo per a=7
$\displaystyle c=3 \;\Rightarrow\; a=9;\quad b=\frac{-25}{20}$ non è intero

Per 4 cifre avremo

$\displaystyle 1000a+100b+10c+d=3(1000d+100c+10b+a)+1;\quad 70b-290c=2999d-997a+1$

che non ha soluzioni intere per b e c compresi tra 0 e 9 per nessuno degli 8 casi possibili per a e d

[Gianfranco]

Testando tutti i numeri fino a $10^7$ se ne trovano solo 2 con la propietà richiesta: 742 e 7425742 da cui si deduce la formulazione generale.

Ottimo risultato Quelo, però, come dice Bruno, ci possono essere anche termini di altro tipo.
Per esempio, proseguendo la ricerca con Maxima da 10^7 a 10^9 ho trovato quest'altro numero: 783742162 che potrebbe generare un'altra famiglia di soluzioni.

max2.png (34.06 KiB) Visto 6517 volte

P.S.
a) per quanto ne so, Maxima non ha due funzioni dedicate a convertire un numero in stringa e viceversa, perciò ho usato due funzioni dispendiose:
sconcat(a,b) che concatena due stringhe - e se sono numeri li trasforma in stringhe, quindi l'ho usata con un solo argomento.
eval_string(a) che valuta una stringa, se contiene solo caratteri numerici restituisce il numero rappresentato.
b) Maxima ha una funzione che inverte una stringa ma non un numero:
sreverse(a)
Per questo motivo il mio programmino è lentissimo, ci ha messo circa mezz'ora a terminare.
---
Domanda: avete implementato un algoritmo più furbo e veloce con il vostro linguaggio di programmazione preferito?

[Bruno]

Per esempio, proseguendo la ricerca con Maxima da 10^7 a 10^9 ho trovato quest'altro numero: 783742162 che potrebbe generare un'altra famiglia di soluzioni.

Sicuramente: da 783742162 si può ottenere un'altra famiglia d'infiniti numeri rispondenti alla richiesta e potremo operare in modo diverso da quello che Sergio ha mostrato.
Abbiamo, infatti:

➁ ➃ ➆ → 742 = 3∙247 + 1
➁ 612 ➃ 738 ➆ → 7 837 4 216 2 = 3 ∙ 2 612 4 738 7 + 1
➁ 612612 ➃ 738738 ➆ → 7 837837 4 216216 2 = 3 ∙ 2 612612 4 738738 7 + 1,

così per i seguenti.
E, in effetti, possiamo verificare che:

$3\cdot \left [2\cdot 10^{6\cdot n+2} + {\Large \frac{68\cdot (10^{3\cdot n}-1)}{111}}\cdot 10^{3\cdot n+2} + 4\cdot 10^{3\cdot n+1}+{\Large \frac{82\cdot (10^{3\cdot n}-1)}{111}}\cdot 10+7 \right ]+1 \\
= \; 7\cdot 10^{6\cdot n+2} + {\Large \frac{31\cdot (10^{3\cdot n}-1)}{37}}\cdot 10^{3\cdot n+2} + 4\cdot 10^{3\cdot n+1}+{\Large \frac{8\cdot (10^{3\cdot n}-1)}{37}}\cdot 10+2$

Potevamo 'fissare' al centro 742 e aggiungere a sinistra e a destra 783 e 162.

[Quelo]

Domanda: avete implementato un algoritmo più furbo e veloce con il vostro linguaggio di programmazione preferito?

Il numero cercato è nella forma $m=3n+1$, quindi $\displaystyle 10^k \le n < \frac{10^{k+1}}{3}$
$n$ comincerà con 1,2 o 3 e terminerà rispettivamente con 3,4,5 o 6,7,8 o 9
Se provo solo numeri che rispettano questa condizione con Decimal Basic ci vogliono circa 5 minuti per le 9 cifre, che significa circa 8 ore per le 11 cifre.
Magari questo fine settimana si può provare

Codice: Seleziona tutto

LET ei = 7
LET ef = 9
DIM a(3,4)
LET a(1,1) = 1
LET a(1,2) = 2
LET a(1,3) = 3
LET a(1,4) = 5
LET a(2,1) = 2
LET a(2,2) = 3
LET a(2,3) = 6
LET a(2,4) = 8
LET a(3,1) = 3
LET a(3,2) = 10/3
LET a(3,3) = 9
LET a(3,4) = 9

LET t = TIME
FOR e = ei-2 TO ef-2
   FOR f = 1 TO 3
      FOR i = a(f,1)*10^e TO a(f,2)*10^e
         FOR h = a(f,3) TO a(f,4)
            LET i$ = STR$(10*i+h)
            LET j = 3*(10*i+h)+1
            LET j$ = STR$(j)
            FOR k = 1 TO LEN(j$)
               IF mid$(j$, LEN(j$)-k+1,1)<>mid$(i$,k,1) THEN
                  LET j=0
                  EXIT FOR
               END IF      
            NEXT K
            IF j > 0 THEN PRINT i$
         NEXT h
      NEXT I
   NEXT F
   PRINT e+2; "cifre:"; TIME-t; "sec."
   LET t = TIME
NEXT E
END

[Quelo]

Anche affinando gli algoritmi, la quantità di numeri da testare aumenta esponenzialmente, quindi ho provato a concentrarmi su una classe di numeri particolarmente promettente, quella che ha al centro il nucleo 247, di cui conosciamo già alcuni elementi:

247 con 3 cifre
261247387 con 9 cifre
24752475247 con 11 cifre
261261247387387 con 15 cifre
2475247524752475247 con 19 cifre
e così via

Tutti questi numeri hanno la forma $\;\displaystyle \underbrace{a_1 a_2 \cdots a_n}_{a}\,247\,\underbrace{b_n \cdots b_2 b_1}_{b\,\text{rovesciato}}$
con $b = 3a$ .

Applicando questi criteri alla ricerca si ottengono 3 nuovi numeri, ibridi delle due famiglie individuate:

24738752475261247
24752612473875247
26124752475247387
con 17 cifre

Ora si tratta di generalizzare.

[Bruno]

Ottimo lavoro, Sergio, molto bello

Rimane il dubbio, senza una dimostrazione, che per tutti i 'candidati' la struttura sia di quel tipo.