Numeri Superdivisibili ...

[franco]

Un numero intero naturale N si dice "superdivisibile" se tutti i numeri formati dalle prime k cifre (da sinistra) sono divisibili per k (con k variabile da 1 al numero n di cifre costituenti N).

Ad esempio, N=12325256 (n=8) è un numero superdivisibile in quanto:
1 è divisibile per 1
12 è divisibile per 2
123 è divisibile per 3
1232 è divisibile per 4
12325 è divisibile per 5
123252 è divisibile per 6
1232525 è divisibile per 7
12325256 è divisibile per 8

Domanda: qual'è il massimo numero superdivisibile?

ciao A313

[Pasquale]

Questo veramente si fa ad occhio (cifra per cifra): -> 98765456405

[franco]

Questo veramente si fa ad occhio (cifra per cifra): -> 98765456405

Ce n'è di più alti!

ciao

[delfo52]

almeno altre due cifre è certamente possibile aggiungerle.
per la divisibilità per 9 e per 10 basta sempre, per definizione aggiungere una cifra; per 11 potremmo essere sfortunati.
Comunque un numero di dieci cifre lo possiamo costruire.
Per averlo più grande possibile cominciamo a riempire le caselle
1: ci mettiamo il 9
2- ci mettiamo 8 (sarebbero andati bene anche gli altri pari)
3- tra 1,4 e 7, mettiamo 7
4- tra 2 e 6, mettiamo 6
5- facile, 5 (oppure lo zero)
6- ci sta solo il 4
7- scelta obbligata, 5
8- si torna a salire, 6
9- qui ci vuole un 4
10- facile : 0
11- qui siamo fortunati, funziona il 5
il prossimo dovrebbe essere divisibile per 3 e per 4, ma le due necessità non si incontrano (per il 3 andrebbero bene 1,4 e 7; per il 4, il 2 e il 6

si tratta di agire sulle caselle a scelta multipla (seconda terza quarta e quinta di sicuro, le altre si vede...)

[franco]

Io sono arrivato a 15 cifre senza particolare difficoltà.
Forse però è stata solo fortuna visto che non ho usato criteri particolari!

ciao

[Pasquale]

Va bene, ho capito: credevo fosse quello, avendo iniziato dalla cifra 9 e continuato con le cifre più alte possibili, non ho pensato che un numero più lungo che inizia con cifre più basse è sempre maggiore di quello con cifre minori pur se inizia con cifre più alte.
O.K. adesso non ho tempo, ma ridarò uno sguardo alla faccenda.

[Sancho Panza]

Questo è il più grande numero superdivisibile che (per ora) sono riuscito a trovare

123258888011145689


Hasta pronto,

Sancho Panza

[Pasquale]

Mi sento di affermare che il numero da 25 cifre 36085 28850 36840 07860 36725 è l'unico e più grande superdivisibile esistente.
Allego un piccolo programma di controllo:

LET a= 3608528850368400786036725
LET a$=STR$(a)
LET lu=LEN(a$)
FOR m=1 TO lu
LET b$=left$(a$,m)
LET b=VAL(b$)
IF MOD(b,m)<> 0 THEN
PRINT "no,";a;"non è un superdivisibile"
GOTO 10
END IF
NEXT M
PRINT "si,";a;"è un superdivisibile"
10
END

[franco]

Io non ho tale potenza di calcolo: bisogna che prima o poi installi e cominci a provare il DecimalBasic.
Con excel, che memorizza solo 15 cifre significative, non riuscivo ad andare oltre.

Anche il sito dove ho pescato questo problema forniva una soluzione a 25 cifre; ad occhio i numeri mi sembrano uguali ma non ho voglia di fare la spunta. Mi fido!

---

Toglimi però un paio di curiosità:
il programmino che hai listato serve per verificare che a sia superdivisibile, ci hai aggiunto un ciclo for-next per incrementarlo di 1 ad ogni giro?
sino a quanto l'hai mandato avanti e quanto c'è voluto per farlo girare?
su decimal basic, quante cifre significative si possono gestire?
bisogna "dichiarare" in qualche modo la variabile perchè possano essere gestite così tante cifre significative?

Scusami se faccio domande un po' così, ho qualche rimembranza di Fortran universitario (con le ultime schede perforate!) e GWbasic con l'Olivetti M24, ma da allora ho smesso di "praticare".

ciao

[Pasquale]

No, attenzione: il programmino lavora su a noto (trovato con altro algoritmo); l'ho messo lì solo per evitare che si dovessero fare 25 divisioni di verifica.
Il ciclo FOR-NEXT effettua tali divisioni sulla prima cifra, sulle prime 2, prime 3, ecc.
Tante volte inserisco cose inutili o mi dilungo su quello che dico, immaginando che potrebbe interessare anche a qualche ragazzo inesperto che si avvicina al forum (tipo me, a parte il ragazzo).

Il Decimal è un programma essenziale che adotta un proprio dialetto e che permette di fare comunque tante cosette utili; tratta numeri interi fino a $2^{3348}$ (1008 cifre, all'incirca un migliaio fra parte intera e decimale).
Con Decimal non è necessario dichiarare le variabili (fa tutto da solo); bisogna solo premere un tasto, in fase di esecuzione, se si sa che il numero trattato supera le 15 cifre (altrimenti non si avrà risultato, o sarà errato).
Insomma è un giochino utile a chi come me non ha studiato altro (nemmeno excel), o per chi ci si vuole divertire; ha un proprio dialetto nell'ambito del Basic e, come tutte le cose, bisogna praticarlo per tirarci fuori qualcosa.

Quindi, la verifica del numero (25 divisioni) la fa in un attimo.
Anche l'altro programma, quello che ho messo giù per individuare il valore di a impiega poco per tirare fuori il risultato (il tempo è funzione delle operazioni che si danno da fare e tutto dipende dall'efficienza dell'algoritmo; ci sono strade più lunghe e strade più brevi): se proprio ti interessa, l'algoritmo sforna il risultato in meno di 1 secondo! (molto più tempo ho impiegato per studiarlo e metterlo giù).
Avevo scritto un programma per tirare giù superdivisibili fino a 30 cifre, ma quando ho visto che non veniva fuori nulla, sono sceso a 29, 28, 27, 26 e finalmente 25 cifre; qui è venuto fuori il risultato unico.
Con meno di 25 cifre esistono molti superdivisibili; ad esempio i superdivisibili a 20 cifre sono ben 44:

10805480103600001800
12005424904858560080
12360600901222567200
14440864504822563660
14480488803690081000
14485808700090082880
22200640209678085240
22560024608422560080
22885248606094567840
24045072304890087020
24085888200010566020
26160688807246564240
30680448304870560640
34200600302442087000
36085288503684007860
38160648900010566000
40285216807290082800
40525240503678082220
42960680103642085800
46240816501236007840
48000688208466084040
48325208404858569060
54045600301294560040
56480480100072009000
56725200004858561860
58565432706046569020
60645696309646565480
64885248901200004280
66325288502466081020
72645656402410567240
74125808108436004200
74440800907200000020
78925288508430084020
80480400308490088860
82285288206030082860
82525248003646560660
84000072607234561840
84045016803678089480
84680472602446567280
90685840509684000060
96360048906030082840
96600008703646560640
96600072602418082260
96685896604836004260

Ecco, questa è una cosa che Decimal è in grado di fare in 0,54 secondi !!!

Qui si capisce meglio l'utilità del programmino di verifica, che ho utilizzato per il controllo dei risultati (anche i programmi errati danno risultati, ma purtroppo sono errati e se non te ne accorgi fai la cappella).

Tempo fa avevo iniziato lo studio del C++, ma poi l'ho abbandonato per mancanza di tempo: peccato, perché il C è più efficiente e veloce.

Un'ultima cosa, che comunque s'era già capita: il risolutore del risultato del quesito del maestro, trasformato poi in quesito del lotto, si chiama naturalmente "Decimal Basic" e non "ad occhio": lo so che le soluzioni "matematiche" sono quelle più attese ed eleganti, ma se un quesito mi dà la possibilità di provare a costruire un programmino Basic, lo faccio, perché mi diverte farlo e lo faccio anche se non mi riesce l'altra strada, perché almeno qualcosa l'ho fatta (meglio che niente).