Sistema numerico a doppia base

Dati due interi positivi coprimi p e q, il sistema numerico a doppia base ( sistema numerico a doppia base in inglese) è un sistema di rappresentazione in cui ogni intero positivo n è rappresentato come una somma di {p, q} - numeri interi, cioè interi della forma p i q j : con = 0 o 1, e i, j numeri interi positivi.
${\ displaystyle n = \ sum _ {i, j} d_ {i, j} p ^ {i} q ^ {j}}$
$d _ {{i, j}}$

Questa è una definizione senza segno, ma esiste anche una definizione con segno che consente termini negativi, dove può anche assumere il valore -1. $d _ {{i, j}}$

Non unicità della rappresentazione

A differenza delle basi singole , una doppia base non garantisce l'unicità della scrittura di un numero. Ad esempio, il numero 127 ha 783 diverse rappresentazioni nella doppia base {2,3}, tra cui: Il numero 10 ha 5 diverse rappresentazioni, 100 ha 402, 1000 ha 1.295.579 e così via.
${\ displaystyle 127 = 2 ^ {2} 3 ^ {3} + 2 ^ {1} 3 ^ {2} + 2 ^ {0} 3 ^ {0} = 2 ^ {2} 3 ^ {3} +2 ^ {4} 3 ^ {0} + 2 ^ {0} 3 ^ {1} = 2 ^ {5} 3 ^ {1} + 2 ^ {0} 3 ^ {3} + 2 ^ {2} 3 ^ {0}}$

Si parla di rappresentazione canonica quando il numero dei termini della somma è il più piccolo possibile. Sopra, le uniche 3 rappresentazioni canoniche del numero 127. Non c'è rappresentazione con meno di 3 termini per 127.

Il numero di rappresentazioni senza segno di un intero è dato dalla seguente funzione ricorsiva: For , $non$
$f (1) = 1$
$n \ ge 1$ ${\ displaystyle f (n) = {\ begin {case} f (n-1) + f (n / 3), & {\ text {si}} n \ equiv 0 {\ pmod {3}} \\ f (n-1), & {\ text {altrimenti.}} \ end {case}}}$

Riferimenti