Due numeri
Che legame c'è tra i due numeri $136$ e $244$ ?
Cordialmente, Alex
Cordialmente, Alex
Risposte
Vero. Ma non è quello. 
E neppure che la somma delle cifre è la stessa: $10$ (mi porto avanti
)
Cordialmente, Alex
E neppure che la somma delle cifre è la stessa: $10$ (mi porto avanti
)Cordialmente, Alex
Allora sono entrambi divisibili per 4 
Scherzum ovviamente!
Scherzum ovviamente!
Più che una proprietà che possiedono entrambi, è proprio un "legame" 
Bravo! 
Cordialmente, Alex
Cordialmente, Alex
E allora doppio bravo per aver compreso il "subdolo" hint
Cordialmente, Alex
Cordialmente, Alex
... però qualcosa mi dice che hai avuto un ausilio elettronico Per completare il quadro ci sarebbero anche ...
In un certo senso, questo problema si ricollega a ...
Cordialmente, Alex
@SuperSquirrell
Cordialmente, Alex
P.S.: che fatica, scrivere
)Cordialmente, Alex
P.S.: che fatica, scrivere
Bongiorno,
ciao.
aldo
ciao.
aldo
Cordialmente, Alex
Cordialmente, Alex
Bel lavoro!
I cubi e le quarte potenze corrispondo a quelli che avevo trovato, per gli altri ne ho verificato qualcuno ma solo sulle catene corte ... per trovare qualche bug eventuale occorre tanta pazienza
Per quanto riguarda i "grandi interi" so che esistono apposite librerie per gestirli.
Cordialmente, Alex
I cubi e le quarte potenze corrispondo a quelli che avevo trovato, per gli altri ne ho verificato qualcuno ma solo sulle catene corte
... per trovare qualche bug eventuale occorre tanta pazienza Per quanto riguarda i "grandi interi" so che esistono apposite librerie per gestirli.
Cordialmente, Alex
Ho aggiornato il codice con un secondo approccio che dovrebbe consentire di arrivare teoricamente fino a $m=18$, ma com'era prevedibile è molto più lento rispetto al precedente.
Questi i risultati per $m=8,9$
Io mi fermo qua, ma se qualcuno vuole mettere il PC a far di conto e postare i risultati per $10<=m<=18$, non ci sono problemi!
Giusto per completezza spiego l'algoritmo adottato:
- l'intervallo da studiare (ossia $n$ nel codice) è stato definito sfruttando il metodo che ho esposto nei precedenti post;
- in entrambe le versioni viene effettuata un'ulteriore scrematura andando a considerare solo i numeri le cui cifre sono in ordine crescente, infatti tutti gli "anagrammi" di un generico $n$ ritornano lo stesso valore di $f()$;
- relativamente alla ricerca delle catene, nella versione 1 vado a creare un array $u$ di $n$ elementi inizializzati a $0$ che mi servirà per identificare immediatamente i "cammini" già percorsi. Infatti assegnando agli $u[n]$ vuoti (ossia pari a $0$) il valore $f(n)$, quando mi imbatto in un elemento non nullo mi fermo subito in quanto ho la certezza che si tratta di una strada già battuta;
- nella versione 2 invece sono costretto a calcolarmi il percorso completo per ogni $n$ considerato. In pratica mi salvo in un vettore il cammino completo che si interrompe quando trovo un doppione; a questo punto modifico il vettore in modo da conservare solo la parte ciclica e se si tratta di una catena "nuova" la metto da parte, altrimenti la scarto.
Pensavo inoltre di ottimizzare la versione 2 inserendo la condizione
nell'if presente nel main(). Ciò comporterebbe un'ulteriore scrematura senza però perdere per la strada nessuna soluzione, infatti in ciascuna catena l'operatore $<=$ risulta verificato almeno una volta tra due elementi consecutivi. Che dite, vi sembra corretto come ragionamento?
Se avete idee circa possibili ottimizzazioni o anche su un diverso algoritmo, fatemi sapere!
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
uint64_t potenza(const uint64_t base, uint64_t esponente)
{
uint64_t r;
for(r = 1; esponente; r *= base, --esponente);
return r;
}
uint64_t fun(uint64_t n, const uint64_t m)
{
uint64_t f_n;
for(f_n = 0; n; f_n += potenza(n % 10, m), n /= 10);
return f_n;
}
bool cifre_crescenti_senza_zeri(uint64_t n)
{
uint64_t s = n % 10;
uint64_t t;
while((t = s) && (n /= 10) && (s = n % 10) && t >= s);
return !n && s;
}
uint64_t get_a(const uint64_t m)
{
uint64_t a;
double b;
for(b = 1 + m * log10(9), a = floor(b); floor(a - log10(a)) <= b; ++a);
return a;
}
uint64_t get_c(uint64_t n)
{
uint64_t c;
for(c = 1; n /= 10; ++c);
return c;
}
void riduci_intervallo(uint64_t &n, const uint64_t m)
{
uint64_t c;
uint64_t temp;
do
{
c = get_c(n);
temp = n;
n = min(n, max(fun(n, m), (c - 1) * potenza(9, m) + potenza(n / potenza(10, c - 1) - 1, m)));
}
while(n != temp);
}
bool trova_elemento(const vector<uint64_t> &v, const uint64_t n)
{
for(uint64_t i = 0; i < v.size(); ++i)
{
if(v[i] == n)
{
return true;
}
}
return false;
}
void trova_catena_1(vector<uint64_t> &v, uint64_t *u, uint64_t n, const uint64_t m)
{
vector<uint64_t> w;
w.push_back(n);
for(; !u[n = u[n] = fun(n, m)]; w.push_back(n));
if(trova_elemento(w, n))
{
v.push_back(n);
}
}
void trova_catena_2(vector<vector<uint64_t>> &w, uint64_t n, const uint64_t m)
{
vector<uint64_t> v;
uint64_t i;
for(; !trova_elemento(v, n); v.push_back(n), n = fun(n, m));
reverse(v.begin(), v.end());
for(i = 0; v[i++] != n;);
v.resize(i);
reverse(v.begin(), v.end());
for(i = 0; i < w.size() && !trova_elemento(w[i], v[0]); ++i);
if(i == w.size())
{
w.push_back(v);
}
}
void stampa_catena_1(uint64_t *u, const uint64_t n)
{
uint64_t i = n;
do
{
cout << " --> " << u[i];
i = u[i];
}
while(i != n);
cout << endl << endl;
}
void stampa_catena_2(const vector<uint64_t> &v)
{
for(uint64_t i = 0; i < v.size(); ++i)
{
cout << " --> " << v[i];
}
cout << endl << endl;
}
int main()
{
const uint64_t m = 8;
uint64_t n = potenza(9, m) * (get_a(m) - 1);
riduci_intervallo(n, m);
/*
//VERSIONE_1 --> max m=7 altrimenti la new fallisce (almeno sul mio PC)
vector<uint64_t> v;
uint64_t *u = new uint64_t[n + 1]();
for(; n; --n)
{
if(!u[n] && cifre_crescenti_senza_zeri(n))
{
trova_catena_1(v, u, n, m);
}
}
cout << "m = " << m << endl << endl;
for(uint64_t i = 0; i < v.size(); ++i)
{
stampa_catena_1(u, v[i]);
}
delete[] u;
*/
//VERSIONE_2 --> versione più lenta, ma in questo caso max m=18 altrimenti si verifica un "overflow" per gli uint64_t
vector<vector<uint64_t>> w;
for(; n; --n)
{
if(cifre_crescenti_senza_zeri(n))
{
trova_catena_2(w, n, m);
}
}
cout << "m = " << m << endl << endl;
for(uint64_t i = 0; i < w.size(); ++i)
{
stampa_catena_2(w[i]);
}
}Questi i risultati per $m=8,9$
m = 8 --> 45196132 --> 45189317 --> 66051462 --> 5495266 --> 47252995 --> 92705541 -- > 49658565 --> 64420580 --> 18978785 --> 105298597 --> 109416966 --> 91197828 -- > 125412933 --> 43516518 --> 19310181 --> 59830502 --> 60612004 --> 3425025 --> 853859 --> 77388964 --> 89882468 --> 111900993 --> 129146727 --> 56321989 --> 10 4947717 --> 60472198 --> 67334147 --> 13353413 --> 482407 --> 22673345 --> 79142 12 --> 48877572 --> 51305252 --> 1178949 --> 108700997 --> 114400261 --> 1810947 --> 65654276 --> 11650691 --> 46796581 --> 69404132 --> 44864227 --> 24418753 - -> 23070532 --> 6169060 --> 48085570 --> 40166019 --> 46471491 --> 50687748 --> 47219811 --> 65654533 --> 4609765 --> 52626915 --> 47187716 --> 35816773 --> 303 90182 --> 59837316 --> 67672102 --> 14889347 --> 82503588 --> 51119715 --> 49592 776 --> 99759077 --> 146825191 --> 61959973 --> 136981767 --> 74719334 --> 54720 518 --> 23389060 --> 61516931 --> 46803142 --> 18594722 --> 66045412 --> 3881186 --> 52017827 --> 28697956 --> 112385572 --> 23330342 --> 92292 --> 86094210 --> 61569346 --> 48548292 --> 77123362 --> 13222853 --> 17181732 --> 28313638 --> 3 5253988 --> 77395781 --> 77515527 --> 18466535 --> 20989796 --> 153362052 --> 24 74501 --> 6286755 --> 26682755 --> 26683011 --> 20143267 --> 7517027 --> 1768528 5 --> 41780356 --> 24684356 --> 20664962 --> 48151617 --> 24677797 --> 67851333 --> 24631942 --> 44864483 --> 35502753 --> 6950054 --> 45573123 --> 6624966 --> 49830977 --> 114472357 --> 12058118 --> 33945316 --> 45202182 --> 17234146 --> 7 582308 --> 39716675 --> 58332742 --> 23011812 --> 16784292 --> 67334403 --> 7595 172 --> 55357830 --> 23727014 --> 11602212 --> 1680387 --> 41005411 --> 521700 - -> 6155683 --> 20924260 --> 44792641 --> 50688003 --> 35631234 --> 2155717 --> 1 2311110 --> 6822 --> 18457344 --> 23135812 --> 17181477 --> 34137158 --> 2301130 2 --> 13636 --> 3372355 --> 6565990 --> 90233924 --> 86172612 --> 25901763 --> 5 0888581 --> 67890115 --> 67658981 --> 86115812 --> 35624932 --> 9514916 --> 88229221 --> 76602178 --> 31666307 --> 10816772 --> 29986692 -- > 149277123 --> 54648934 --> 62097347 --> 56328292 --> 61901507 --> 50881765 --> 41780100 --> 22607555 --> 8616804 --> 36979201 --> 93544677 --> 56784197 --> 73 489317 --> 71432198 --> 65661093 --> 48482756 --> 41520802 --> 17233890 --> 6560 2117 --> 24678051 --> 88593477 --> 24678050 --> 54642372 --> 7973187 --> 77124902 --> 1 Process returned 0 (0x0) execution time : 28.730 s Press any key to continue.
m = 9 --> 62763635 --> 72579698 --> 1001797253 --> 470101025 --> 42569390 --> 7871541 38 --> 351377624 --> 93040058 --> 523873169 --> 574062524 --> 54862865 --> 29275 9754 --> 859717610 --> 614376254 --> 63006608 --> 164470499 --> 826058714 --> 32 1082541 --> 136453706 --> 389778106 --> 746660539 --> 460242136 --> 20700388 --> 308809258 --> 792046 993 --> 1212975109 --> 817148737 --> 921371355 --> 431720226 --> 50714667 --> 103077876 --> 265375929 --> 829199 238 --> 1430717631 --> 91086423 --> 531998253 --> 913004835 --> 523892853 --> 65 9802585 --> 671793528 --> 614396448 --> 542599725 --> 821317128 --> 308809773 -- > 736602525 --> 64435956 --> 412026102 --> 10341378 --> 174872847 --> 390021078 --> 562012020 --> 12032358 --> 136211244 --> 10622694 --> 407839050 --> 56422677 6 --> 113156595 --> 403377246 --> 91349076 --> 825554109 --> 527760249 --> 48042 1692 --> 532241226 --> 12314697 --> 438134133 --> 134820750 --> 176806800 --> 32 8944456 --> 534475665 --> 66912345 --> 409811346 --> 532259886 --> 669860598 --> 1075462647 --> 103340532 --> 2274831 --> 174854187 --> 351620085 --> 148221870 --> 309052233 --> 389433687 --> 706608441 --> 195251016 --> 401404950 --> 390160 047 --> 438133620 --> 144617130 --> 50975277 --> 512388072 --> 310762896 --> 582 167412 --> 186865326 --> 300641865 --> 156608073 --> 196699536 --> 1194467364 -- > 448735605 --> 189099252 --> 1298433345 --> 524175192 --> 431943516 --> 4000149 66 --> 408100170 --> 174833481 --> 309352719 --> 817187589 --> 872734014 --> 215 469426 --> 410054319 --> 389917587 --> 1125956457 --> 443973825 --> 564509115 -- > 403619706 --> 448211316 --> 144839910 --> 909602679 --> 1222770978 --> 6427005 75 --> 94953816 --> 526069268 --> 553825454 --> 142574711 --> 83185142 --> 270670922 --> 478206 935 --> 574304984 --> 564751064 --> 64939538 --> 921391037 --> 815234465 --> 148 746158 --> 321344174 --> 41179919 --> 1202877221 --> 214926992 --> 1172602844 -- > 185174345 --> 179021558 --> 565898588 --> 940228472 --> 562517648 --> 19889563 4 --> 1055589083 --> 661735004 --> 62743952 --> 440087768 --> 359744654 --> 4425 64157 --> 55124498 --> 433916322 --> 397820403 --> 562293846 --> 544029585 --> 528022392 --> 52361 3073 --> 52443990 --> 777338586 --> 401566464 --> 32972646 --> 448212339 --> 522 202896 --> 533671086 --> 196719219 --> 1212693285 --> 533690259 --> 788864802 -- > 587564871 --> 363388761 --> 329003505 --> 391366617 --> 458046552 --> 15067959 9 --> 1216599021 --> 786872826 --> 503516814 --> 148483503 --> 270952236 --> 439 826136 --> 542095632 --> 401687286 --> 329207112 --> 427795317 --> 510716775 --> 135044769 --> 440348889 --> 790879788 --> 1298554983 --> 1047465024 --> 5317137 3 --> 82719390 --> 949432509 --> 1164759075 --> 482373795 --> 604600578 --> 1969 41996 --> 1570099494 --> 1205092488 --> 658072239 --> 574043352 --> 44824023 --> 135024867 --> 186884496 --> 810753354 --> 178779096 --> 1040197224 --> 42829941 0 --> 909584019 --> 1298694465 --> 931692024 --> 785201526 --> 188556306 --> 292 516782 --> 574024182 --> 177049773 --> 549116745 --> 442282332 --> 134783430 --> 175154673 --> 94972989 --> 1724515947 --> 472558755 --> 223000098 --> 521658924 --> 535885332 --> 274354392 --> 430291899 --> 1296761535 --> 451855935 --> 5297 32545 --> 1162282687 --> 328945993 --> 1298734342 --> 562556503 --> 27988087 --> 8707 81399 --> 1124003332 --> 322219 --> 387441709 --> 602889403 --> 666215980 --> 55 3824943 --> 526108633 --> 156366124 --> 32468554 --> 148746157 --> 227480053 --> 176807311 --> 225022324 --> 2237512 --> 42327952 --> 430010584 --> 136714825 -- > 186884497 --> 841029265 --> 533932207 --> 429787294 --> 990291232 --> 534494836 --> 52666768 --> 216835756 --> 198653173 --> 574062013 --> 144839908 --> 1043820406 --> 54639064 --> 410072977 --> 508743967 --> 614658079 --> 584362486 --> 291088 456 --> 668149423 --> 542338093 --> 523913047 --> 430029244 --> 388227628 --> 45 3105706 --> 54619381 --> 533950867 --> 576015136 --> 64434934 --> 398586127 --> 708260569 --> 584100853 --> 272623534 --> 52687474 --> 227480563 --> 186885007 - -> 455037613 --> 738798623 --> 746680733 --> 235381844 --> 270952748 --> 604561724 --> 62986 925 --> 931168247 --> 572351861 --> 188575478 --> 487528793 --> 146511208 --> 468672187 --> 369560719 --> 837322786 --> 359260756 --> 451855933 --> 52779 9103 --> 857521513 --> 180450907 --> 564207094 --> 440329717 --> 409589079 --> 1339048071 --> 562293336 --> 951385123 --> 525584347 --> 180975193 --> 912985153 --> 472335975 --> 756738746 --> 277668893 --> 1 Process returned 0 (0x0) execution time : 215.905 s Press any key to continue.
Io mi fermo qua, ma se qualcuno vuole mettere il PC a far di conto e postare i risultati per $10<=m<=18$, non ci sono problemi!
Giusto per completezza spiego l'algoritmo adottato:
- l'intervallo da studiare (ossia $n$ nel codice) è stato definito sfruttando il metodo che ho esposto nei precedenti post;
- in entrambe le versioni viene effettuata un'ulteriore scrematura andando a considerare solo i numeri le cui cifre sono in ordine crescente, infatti tutti gli "anagrammi" di un generico $n$ ritornano lo stesso valore di $f()$;
- relativamente alla ricerca delle catene, nella versione 1 vado a creare un array $u$ di $n$ elementi inizializzati a $0$ che mi servirà per identificare immediatamente i "cammini" già percorsi. Infatti assegnando agli $u[n]$ vuoti (ossia pari a $0$) il valore $f(n)$, quando mi imbatto in un elemento non nullo mi fermo subito in quanto ho la certezza che si tratta di una strada già battuta;
- nella versione 2 invece sono costretto a calcolarmi il percorso completo per ogni $n$ considerato. In pratica mi salvo in un vettore il cammino completo che si interrompe quando trovo un doppione; a questo punto modifico il vettore in modo da conservare solo la parte ciclica e se si tratta di una catena "nuova" la metto da parte, altrimenti la scarto.
Pensavo inoltre di ottimizzare la versione 2 inserendo la condizione
n <= fun(n, m)
nell'if presente nel main(). Ciò comporterebbe un'ulteriore scrematura senza però perdere per la strada nessuna soluzione, infatti in ciascuna catena l'operatore $<=$ risulta verificato almeno una volta tra due elementi consecutivi. Che dite, vi sembra corretto come ragionamento?
Se avete idee circa possibili ottimizzazioni o anche su un diverso algoritmo, fatemi sapere!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo