Don't take life too seriously: it's just a temporary situation

Takeuchi (numeri di)

Sequenze  Teoria dell'informazione 

Nel 1978 I. Takeuchi propose la seguente funzione: Definizione della funzione di Takeuchi

A dispetto della sua apparente complessità, la funzione si riduce a Valore della funzione di Takeuchi

 

La funzione viene utilizzata per valutare le prestazioni di elaboratori elettronici, soprattutto nel caso di programmazione in linguaggi funzionali come il LISP; calcolarla tramite la definizione, infatti, comporta un enorme numero di passaggi, mentre la definizione alternativa permette di verificare facilmente l’esattezza del risultato. Supponendo che il calcolatore “dimentichi” i valori già calcolati e calcoli la funzione secondo la definizione, anche a costo di ricalcolare più volte il valore con gli stessi argomenti, il numero di volte che viene eseguita la parte “altrimenti” nel calcolare f(n, 0, n + 1) (che vale n + 1, ma non è rilevante), per n intero non negativo, si chiama “numero di Takeuchi” Tn.

 

La tabella seguente mostra i valori di Tn per n sino a 20.

n

Tn

0

0

1

1

2

4

3

14

4

53

5

223

6

1034

7

5221

8

28437

9

165859

10

1029803

11

6772850

12

46983238

13

342509396

14

2615606677

15

20865444825

16

173446634597

17

1499111445237

18

13445550920288

19

124919896067530

20

1200320663197275

 

I numeri di Takeuchi possono essere calcolati con la ricorrenza scoperta da Donald Ervin Knuth: T0 = 0, Ricorrenza per il calcolo dei numeri di Takeuchi, o con la ricorrenza equivalente Ricorrenza per il calcolo dei numeri di Takeuchi, dove Cn è un numero di Catalan.

 

Knuth dimostrò nel 1991 che:

  • la funzione generatrice dei numeri di Takeuchi f(x) soddisfa l’equazione funzionale Equazione funzionale soddisfatta dalla funzione generatrice dei numeri di Takeuchi;

  • enlognnnloglogn < Tn < enlognn + logn, per n abbastanza grande;

  • ogni numero di Takeuchi a partire da T2 = 4 è maggiore del corrispondente numero di Bell.

 

Thomas Prellberg avanzò nel 2000 la congettura che Tn tenda a Limite asintotico cui tendono i numeri di Takeuchi, dove bn è l’n-esimo numero di Bell e c è la costante di Takeuchi – Prellberg.

Tabelle numeriche

I valori di Tn per n sino a 100.

Bibliografia

  • Knuth, Donald Ervin;  Artificial Intelligence and Theory of Computation, Londra, Academic Press, 1991.
  • Prellberg, Thomas;  "On the Asymptotics of Takeuchi Numbers" in Symbolic Computation, Number Theory, Special Functions, Physics and Combinatorics, Dordrecht, Kluver, pag. 231 – 242, 2001.

Contattami

Potete contattarmi al seguente indirizzo bitman[at]bitman.name per suggerimenti o segnalazioni d'errori relativi a questo articolo.