Primi quadratici

Dal Progetto Eulero

Problema 27:

Eulero scoprì la notevole formula quadratica:

n² + n + 41

Risulta che la formula genera 40 numeri primi per valori consecutivi n = 0 a 39. Comunque, quando n = 40, 40² + 40 + 41 = 40(40 + 1) + 41 è divisibile per 41, e senza dubbio quando n = 41, 41² + 41 + 41 è chiaramente divisibile per 41.

Fu scoperta l’incredibile formula n² − 79n + 1601, che genera 80 primi per valori consecutivi di n = 0 a 79. Il prodotto dei coefficienti, −79 e 1601, è −126479.

Considerando le quadratiche della forma:

n² + an + b, dove |a| < 1000 e |b| < 1000 dove |n| è il moduo/valore assoluto di n cioè |11| = 11 e |−4| = 4 Trova il prodotto dei coefficienti, a e b, per l'espressione quadratica che genera il massimo numero di primi per valori consecutivi di n, partendo con n = 0.

risolto

luni66

Cicli dei reciproci

Dal Progetto Eulero

Problema 26:

Una frazione unitaria contiene 1 al numeratore. La rappresentazione decimale della frazione unitaria con denominatori da 2 a 10 sono:

1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1

Dove 0.1(6) significa 0.166666…, e ha un ciclo ricorrente di 1 cifra. Può essere verificato che 1/7 ha un ciclo ricorrente di 6 cifre.

Trova il valore di d < 1000 per cui 1/d contiene il più lungo del ciclo ricorrente nella sua parte frazionaria decimale.

risolto

circa 0.01 secondi per ottenerlo, ho anche sfruttato che “The period of 1/k for integer k is always ≤ k − 1.” da Repeating decimal

luni66

Il numero di Fibonacci con 1000 cifre

Dal Progetto Eulero

Problema 25:

La sequenza di Fibonacci è definita come la relazione ricorsiva:

Fn = Fn−1 + Fn−2, dove F1 = 1 e F2 = 1.
Quindi i primi 12 termini saranno:

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
Il 12° termine, F12, è il primo termine che contiene 3 cifre.

Qual è il primo termine nella sequenza di Fibonacci che contiene 1000 cifre?

risolto

circa 0.05 secondi per ottenerlo

luni66

Permutazioni lessicografiche

Dal Progetto Eulero

Problema 24:

Una permutazione è una disposizione ordinata di oggetti. Per esempio, 3124 è una possibile permutazione delle cifre 1, 2, 3 e 4. Quando tutte le permutazioni sono elencati numericamente o alfabeticamente, è detto ordine lessicografico. Le permutazioni lessicografiche di 0, 1 e 2 sono:

012 021 102 120 201 210

Qual è la milionesima permutazione lessicografica delle cifre 0, 1, 2, 3, 4, 5, 6, 7, 8 e 9?

risolto

molto interessante, ho implementato l’algoritmo Steinhaus–Johnson–Trotter, ho trovato molto utili le pagine Johnson-Trotter Algorithm Listing All Permutations and Steinhaus Johnson Trotter permutation algorithm explained and implemented in Java
questo algoritmo è molto efficiente, solo circa 2 secondi per trovare tutte le permutazioni, cioè 10! = 3628800

luni66

Somma di numeri non abbondanti

Dal Progetto Eulero

Problema 23:

Un numero perfetto è un numero per cui la somma dei suoi divisori propri è esattamente uguale al numero stesso. Per esempio, la somma dei divisori propri di 28 è 1 + 2 + 4 + 7 + 14 = 28, che significa che 28 è un numero perfetto.

Un numero n è detto difettivo se la somma dei suoi divisori propri è minore di n ed è detto abbondante se questa somma supera n.

Poiché 12 è il numero abbondante più piccolo, 1 + 2 + 3 + 4 + 6 = 16, il numero più piccolo che può essere scritto come somma di due numeri abbondanti è 24. Dall’analisi matematica, si può dimostrare che tutti i numeri interi maggiori di 28123 possono essere scritti come somma di due numeri abbondanti. Tuttavia non è possibile ridurre questo limite superiore con una ulteriore analisi anche se è noto che il numero più grande che non può essere espresso come somma di due numeri abbondanti è minore di questo limite.

Trova la somma di tutti i numeri interi positivi che non possono essere espressi come la somma di due numeri abbondanti.

risolto

luni66

I punteggi dei nomi

Dal Progetto Eulero

Problema 22:

Usando […] un file di testo di 46K contenente oltre cinquemila nomi, comincia con l’ordinarli alfabeticamente. Poi calcola il valore alfabetico di ciascun nome, moltiplica questo valore per la sua posizione alfabetica nella lista per ottenere il punteggio del nome.

Per esempio, quando la lista è ordinata afabeticamente, COLIN, che è pari a 3 + 15 + 12 + 9 + 14 = 53, è il 938° nome nella lista. Così, COLIN otterrebbe un punteggio di 938 × 53 = 49714.

Qual è il totale di tutti i punteggi dei nome nel file?

risolto

luni66

Numeri amicabili

Dal Progetto Eulero

Problema 21:

Definiamo d(n) come la somma dei divisori propi di n (numeri minori di n che dividono esattamente n);
Se d(a) = b e d(b) = a, dove a ≠ b, allora a e b sono una coppia di numeri amicabili e a e b sono chiamati numeri amicabili.

Per esempio, i divisori propi di 200 sono 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 e 110; quindi d(220) = 284. I divisori propi di 284 sono 1, 2, 4, 71 e 142; quindi d(284) = 220.

Calcola la somma di tutti i numeri amicabili inferiori a 10000.

risolto

Ho trovato questo problema il più difficile fra i primi 21, senza usare alcun teorema come quello di Thābit ibn Qurra.
Qui ho trovato conveniente l’uso della classe java PriorityQueue.

luni66

Somma delle cifre di un fattoriale

Dal Progetto Eulero

Problema 20:

n! significa n * (n – 1) * … * 3 * 2 * 1

Per esempio, 10! = 10 * 9 … * 3 * 2 * 1 = 3628800,
e la somma delle cifre del numero 10! è 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Trova la somma delle cifre del numero 100!

risolto

luni66

Contare le domeniche

Dal Progetto Eulero

Problema 19:

Ti sono date le seguenti informazioni, ma tu potresti preferire fare una qualche ricerca per tuo conto.

  • 1 gennaio 1900 era un lunedì.
  • Trenta giorni hanno settembre,
    aprile, giugno e novembre.
    Tutti gli altri ne hanno trentuno,
    tranne febbraio,
    che ne ha ventotto, pioggia o sole.
    e negli anni bisestitli, ventinove.
  • Un anno bisestile avviene negli anni divisibile per 4, ma non a inizio secolo a meno che non sia divisibile per 400.

Quante domeniche cadono il primo del mese durante il ventesimo secolo (dal 1 gennaio 1901 al 31 dicembre 2000)?

risolto

Senza usare le classi Calendar e Date in Java.

luni66

Somma massima in un percorso

Dal Progetto Eulero

Problema 18:
Iniziando dal vertice del triangolo sottostante e spostandosi sui numeri adiacenti nella riga sotto, la somma totale più grande da cima a fondo è 23.

3
7 4
2 4 6
8 5 9 3

Cioè, 3 + 7 + 4 + 9 = 23.

Trova il totale massimo da cima a fondo del triangolo sotto:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTA: Essendoci solo 16384 percorsi, è possibile risolvere questo problema verificando ogni percorso. Comunque, il Problema 67 è la stessa sfida ma con un triangolo contenente cento righe, non può essere risolto con la forza bruta, e richiede un metodo intelligente! ;o)

risolto

Naturalmente ho risolto con lo stesso metodo anche il Problema 67.

luni66