Il numero di modi in cui un numero naturale $n$ può essere ottenuto come somma di numeri naturali è $2^{n-1}$
Facciamo l'esempio del numero 3, i modi sono 4: 3, 2+1, 1+2, 1+1+1
Possiamo semplificare la determinazione aiutandoci con i numeri binari
Consideriamo $n-1$ bit: 00, 01, 10, 11
0 è la somma interna (accorpamento)
1 è la somma esterna
Il tutto associato a $n$ unità: 1 (b1) 1 (b0) 1
Nel nostro caso
00: 1(+)1(+)1 = 3
01: 1(+)1 + 1 = 2+1
10: 1 + 1(+)1 = 1+2
11: 1 + 1 + 1 = 1+1+1
Automatizzando il processo ricaviamo i modi per qualsiasi numero (avendo tempo a sufficienza)
Dobbiamo considerare le combinazioni che contengono solo numeri primi (per il 3 da quattro si passa a 1), ma comunque la progressione rimane di tipo esponenziale
Se la parità si ha per il 17, tutti i primi maggiori di 17 avranno un numero di modi che è maggiore del primo stesso, analogamente per quelli minori
Codice: Seleziona tutto
primo modi
2 1
3 1
5 2
7 3
11 6
13 9
17 17
19 23
23 40
29 87
31 111
Codice: Seleziona tutto
from primality.primality import isprime as isp
p = [2,3]
for n in range(1,6):
for j in range(-1,2,2):
m = 6*n+j
if isp(m):
f = []
p.append(m)
for i in range(0,2**(m-2)-1,2):
b = bin(i)[2:].rjust(m-1,'0')
d = 1
e = []
if b.find('11')==-1:
for c in list(b):
if c=='0':
d += 1
else:
e.append(d)
d = 1
e.append(d)
if set(e)-set(p)==set() and sorted(e) not in f:
f.append(sorted(e))
print(m, len(f))