Rappresentazione dei fatti

Descriverò una rappresentazione di numeri che ho inventato qualche tempo fa e farò una domanda aperta a riguardo.

La rappresentazione, che chiamerò “Factparen” (abbreviazione di Parentesi di fattorizzazione), assegna ogni numero intero maggiore di 0 a una stringa univoca di parentesi chiuse correttamente, e ogni stringa di parentesi chiuse correttamente a un numero intero. Be ‘quasi. Un’altra regola è che questo esclude stringhe come “() (())”, che possono essere separate in più stringhe di parentesi chiuse correttamente (“()” e “(())”).

L’algoritmo funziona come segue:

132

(2,1,0,0,1)

(2,1 ,,, 1)

(2 1 1 3 1)

((()) () () (() ()) ())

Passaggio 1: prendere il numero e fattorizzarlo. Ad esempio, per 132, la fattorizzazione è 2² * 3 * 11. Aggiungiamo anche i fattori che sono alla potenza di 0 (fino al più grande fattore diverso da zero), come tale: 2² * 3¹ * 5⁰ * 7⁰ * 11¹. Annota solo gli esponenti tra parentesi separati da virgole, così possiamo ottenere (2,1,0,0,1).

Passaggio 2: rimuovere tutti gli esponenti di 0, mantenendo le virgole. Quindi otteniamo (2,1 ,,, 1).

Passaggio 3: Sostituisci tutte le stringhe di virgole con quante virgole ci sono nella stringa, come otteniamo (2 1 1 3 1).

Passaggio 4: applicare il passaggio 1 a tutti i numeri all’interno ricorsivamente, fino a quando non rimangono più numeri. Il numero 1 è scritto semplicemente come “()”. Il risultato finale sarà ((()) () () (() ()) ()).

Rappresentazione unica

Ovviamente la fattorizzazione di un numero naturale è unica e come tale la rappresentazione nel passaggio 2 è unica. La conversione delle virgole in numeri per raggiungere il passaggio 3 potrebbe sembrare un po ‘confusa, poiché non siamo sicuri che il primo numero corrisponda a un numero di virgole o a un esponente. Tuttavia, questo non è il caso, in quanto può essere dedotto semplicemente guardando quanti numeri ci sono. Se esiste un numero pari di numeri, il primo numero deve corrispondere a un numero di virgole (ad esempio, 27 è scritto nel passaggio 3 come “(1 3)” e corrisponde a “(, 3)”). Se c’è un numero dispari di numeri, il primo numero corrisponde a un esponente (come per 6, che è scritto nel passaggio 3 come “(1 1 1)” e corrisponde a “(1,1)”).

Come tale, la funzione Factparen è reversibile, e di fatto biiettiva. Per ogni stringa di parentesi correttamente costruita c’è un numero e per ogni numero c’è una stringa di parentesi correttamente costruita.

Proprietà

I primi numeri di Factparen sono:

1 ()
2 (())
3 (() ())
4 ((()))
5 ((()) ())
6 (() () ())
7 ((() ()) ())
8 ((() ()))
9 (() (()))
10 (() (()) ())
11 (((())) ())
12 ((()) () ())
13 (((()) ()) ())
14 (() (() ()) ())
15 (() () () ())
16 (((())))
17 ((() () ()) ())
18 (() () (()))
19 (((() ()) ()) ())
20 ((()) (()) ())

Una proprietà interessante è che, a causa della sua struttura ricorsiva, alcuni (ma non tutti) tutti i grandi numeri possono essere scritti molto rapidamente. Ad esempio, eseguendo l’algoritmo sul numero

115792089237316195423570985008687907853269984665640564039457584007913129639936

dà il risultato

((((() ()))))

Perché? Perché il numero indicato è uguale a 2²⁵⁶, che può essere scritto in modo abbastanza elegante in questo modo. In effetti, per il numero 2 ^ (2²⁵⁶), che ha circa 10⁷⁶ cifre e come tale non scriverò per intero, la stringa è semplicemente

(((((() ())))))

In generale, per una stringa x, (x) è uguale a 2 ^ x. Pertanto, per 2n caratteri, il numero più grande che può essere scritto è (((((())) …))), dove ogni parte ha n parentesi. Questo è uguale a 2 ^ 2 ^ 2 ^ 2 ^… ^ 2, n-1 volte. Inutile dire che questo cresce abbastanza velocemente.

Domanda aperta

Ma che dire del più piccolo? Qual è il numero più piccolo che può essere scritto nella rappresentazione Factparen in caratteri 2n?

Per n = 1, 2, 3,…, i primi 20 termini sono, come segue,

1, 2, 3, 5, 7, 13, 19, 38, 69, 138, 217, 395, 581, 1162, 1957, 3781, 7383, 14559, 24521, 49042

L’ultimo termine è nell’illustrazione all’inizio dell’articolo.

Non vedo schemi evidenti in questa sequenza. La fattorizzazione di questi termini fornisce alcuni risultati piuttosto strani

1, 2, 3, 5, 7, 13, 19, 2 * 19, 3 * 23, 2 * 3 * 23, 7 * 31, 5 * 79, 7 * 83, 2 * 7 * 83, 19 * 103, 19 * 199, 3 * 23 * 107, 3 * 23 * 211. 7 * 31 * 113, 2 * 7 * 31 * 113

Sembra che piacciano i numeri con una piccola quantità di fattori, ma i numeri primi reali tendono a non vincere. La sequenza sembra crescere un po ‘più lentamente di 2 ^ x, a circa 1,7160 ^ n.

La mia domanda è anche se esiste un algoritmo efficiente per calcolare quei numeri. Il backtracking alla fine calcolerà questi numeri con precisione, ma ci vorrà molto tempo per numeri più grandi.

La mia ipotesi è che sia davvero difficile rispondere, così come la maggior parte dei problemi legati ai numeri primi e alla fattorizzazione in generale. Ad ogni modo trovo interessante questa notazione di numeri e domande correlate e spero che lo faccia anche tu.

Aggiornamento: Factparen generalizzato

Come ho detto all’inizio, Factparen funziona per ogni stringa di parentesi che si chiude correttamente e che non può essere divisa in parti più piccole. Ma che dire di quelli che possono?

Bene, si scopre che Factparen può essere generalizzato a tutti i numeri razionali non negativi, in modo che a tutte le stringhe corrette sia assegnato un numero.

Innanzitutto, un caso limite. Dobbiamo ancora definire il numero a cui “”, la stringa vuota, corrisponde. Per convenzione, definirò che la stringa vuota sarà uguale a 0.

Ora per mostrare il metodo, scegliamo una nuova stringa.

(() () ()) () (())

Innanzitutto, applica il solito Factparen su tutte le parti più piccole. Otterremo

{6, 1, 2}

Il mio primo istinto è stato quello di dire che il primo numero è il numeratore e di considerare ogni altro numero il denominatore. In quanto tale, {6, 1, 2} sarebbe uguale a 6 / (1 2), o 6 / (, 2), o, 6/9, in altre parole 2/3. Voilá, l’abbiamo risolto!

O abbiamo? Vedi, il problema con questo metodo è che (() () ()) () (()) è 2/3, ma lo è anche (()) () (). Abbiamo dichiarato all’inizio che ogni numero deve corrispondere a una stringa univoca, quindi non va bene.

Tuttavia, c’è un modo per evitarlo. Mentre scrivi il denominatore, salta i fattori primi che appaiono già nel numeratore. Quindi, ad esempio, 6 = 2 * 3, quindi nell’interpretazione (1 2) non sarà uguale a 3², ma a 7².

Si noti che questo viene fatto solo al primo livello, non in modo ricorsivo. Saltiamo i fattori 2 e 3 durante l’interpretazione (1 2), ma non nell’interpretazione di “1” e “2” (o “()” e “(())”). In questo modo, la stringa “(() () ()) () (())” sarà uguale a 6/49.

Poiché ogni frazione irriducibile è distinta, questo metodo è biiettivo, quindi ogni numero razionale non negativo ha una stringa corrispondente di parentesi chiuse correttamente e viceversa. Il Factparen normale è un caso speciale di Factparen generalizzato.

Aggiornamento: convertitore Haskell

Ecco un convertitore scritto in Haskell sia da e verso Factparen generalizzato. Tieni presente che sono nuovo nella lingua, quindi probabilmente una buona parte di essa potrebbe essere stata scritta meglio, ma per quanto ne so, dovrebbe funzionare correttamente in tutti i casi.