Funzione di Kempner

Grafico della funzione di Kempner

Nella teoria dei numeri, la funzione di Kempner ${\displaystyle S(n)}$[1] è definita per un dato numero naturale ${\displaystyle n}$ come il più piccolo numero ${\displaystyle s}$ tale che ${\displaystyle n}$ divida il fattoriale ${\displaystyle s!}$. [2] Per esempio, il numero ${\displaystyle 8}$ non divide ${\displaystyle 1!}$, ${\displaystyle 2!}$, ${\displaystyle 3!}$, ma è un divisore di ${\displaystyle 4!}$, quindi ${\displaystyle S(8)=4}$. Questa funzione ha la proprietà di crescere linearmente sui numeri primi ma meno che logaritmicamente sui numeri fattoriali.

Storia

Questa funzione fu per la prima volta considerata da François Édouard Anatole Lucas nel 1883,[3] seguito da Joseph J. B. Neuberg nel 1887.[4] Nel 1918, A. J. Kempner fornì il primo algoritmo per calcolare ${\displaystyle S(n)}$.[5] Florentin Smarandache la riscoprì nel 1980[6], motivo per cui qualche volta è chiamata "funzione di Smarandache".[7][8][9][10]

Proprietà

Dal momento che ${\displaystyle n}$ divide ${\displaystyle n!}$, il valore di ${\displaystyle S(n)}$ è al massimo ${\displaystyle n}$. Un numero ${\displaystyle n>4}$ è un numero primo se e solo se ${\displaystyle S(n)=n}$.[11] Cioè, i numeri ${\displaystyle n}$ per cui ${\displaystyle S(n)}$ è il più grande possibile relativamente a ${\displaystyle n}$ sono i numeri primi. D'altra parte, i numeri per cui ${\displaystyle S(n)}$ è il più piccolo possibile sono i fattoriali: ${\displaystyle S(k!)=k}$, per ogni ${\displaystyle k\geq 1}$.

${\displaystyle S(n)}$ è il più piccolo grado possibile di un polinomio monico a coefficienti interi tale che i valori assunti sugli interi siano tutti divisibili per ${\displaystyle n}$.[1] Per esempio, il fatto che ${\displaystyle S(6)=3}$ significa che c'è un polinomio cubico i cui valori sono tutti zero modulo 6, come

${\displaystyle x(x-1)(x-2)=x^{3}-3x^{2}+2x,}$

ma che tutti i polinomi quadratici e lineari (con il coefficiente direttore uguale a 1) sono diversi da 0 modulo 6 per qualche intero.

In uno dei problemi avanzati del American Mathematical Monthly, proposto nel 1991 e risolto nel 1994, Paul Erdős osservò che la funzione ${\displaystyle S(n)}$ coincide con il maggiore fattore primo di ${\displaystyle n}$ per "quasi tutti" gli interi (nel senso che la densità asintotica dell'insieme delle eccezioni è zero).[12]

Complessità computazionale

La funzione di Kempner ${\displaystyle S(n)}$ per un numero arbitrario ${\displaystyle n}$ è il massimo di ${\displaystyle S(p^{e})}$, con ${\displaystyle p^{e}}$ le potenze prime che dividono ${\displaystyle n}$.[5] Dove ${\displaystyle n}$ è esso stesso una potenza prima ${\displaystyle p^{e}}$, si può trovare la sua funzione di Kempner in tempo polinomiale analizzando sequenzialmente i multipli di ${\displaystyle p}$ finché non si trova quello più piccolo tale che il suo fattoriale contenga abbastanza multipli di ${\displaystyle p}$. Lo stesso algoritmo può essere esteso a ogni ${\displaystyle n}$ di cui si conosce la fattorizzazione, applicandolo separatamente ad ogni potenza prima nella fattorizzazione e scegliendo quella che conduce al valore più grande.

Per un numero nella forma ${\displaystyle n=px}$, dove ${\displaystyle p}$ è primo e ${\displaystyle x}$ è minore di ${\displaystyle p}$, la funzione di Kempner di ${\displaystyle n}$ assume il valore ${\displaystyle p}$.[5] Segue che calcolare della funzione di Kempner per un numero semiprimo (un prodotto di due primi) è computazionalmente equivalente al trovare la sua fattorizzazione in primi, che al momento sembra essere un problema complesso. Più in generale, ogni volta che ${\displaystyle n}$ è un numero composto, il massimo comun divisore tra ${\displaystyle S(n)}$ e ${\displaystyle n}$ sarà un divisore non banale di ${\displaystyle n}$, permettendo la fattorizzazione di ${\displaystyle n}$ attraverso ripetute valutazioni della funzione di Kempner. Pertanto, il calcolo della funzione di kempner può in generale non essere più semplice di fattorizzare un numero composto.

Serie associate

Molte serie costruite a partire da ${\displaystyle S(n)}$ si sono rivelate convergenti.[13][14][15][16] Nel caso di ${\displaystyle S(n)}$, nella letteratura ci si riferisce alle serie come costanti di Smarandache, anche quando esse dipendono da dei parametri ausiliari. Da notare anche che esse differiscono dalle costanti di Smarandache che derivano dalla sua generalizzazione della congettura di Andrica. Le seguenti sono esempi di tali serie:

• ${\displaystyle \sum _{n=2}^{\infty }{\frac {1}{S(n)!}}=1,09317\ldots }$ OEIS:A048799.
• ${\displaystyle \sum _{n=2}^{\infty }{\frac {S(n)}{n!}}=1,71400629359162\ldots }$ OEIS:A048834 e è irrazionale.
• ${\displaystyle \sum _{n=2}^{\infty }{\frac {1}{\prod _{i=2}^{n}S(i)}}=0,719960700043\ldots }$ OEIS:A048835.
• ${\displaystyle \sum _{n}S(n)^{-\alpha }{S(n)!}^{-1/2}<\infty ,\,{\text{ con }}\alpha >1.}$

Note

1. Chiamata "numeri di Kempner" nella On-Line Encyclopedia of Integer Sequences: vedere Sloane, N.J.A. (ed.). "Sequence A002034 (Kempner numbers: smallest number m such that n divides m!)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation
2. "Smarandache function", PlanetMath
3. E. Lucas, Question Nr. 288, in Mathesis, vol. 3, 1883, p. 232.
4. J. Neuberg, Solutions de questions proposées, Question Nr. 288, in Mathesis, vol. 7, 1887, pp. 68–69.
5. A. J. Kempner, Miscellanea, in American Mathematical Monthly, vol. 25, n. 5, 1918, pp. 201–210, DOI:10.2307/2972639, JSTOR 2972639.
6. F. Smarandache, A function in number theory, in An. Univ. Timisoara, Ser. St. Mat., vol. 18, 1980, pp. 79–88, MR 0619740, arXiv:math/0405143.
7. Jonathan Sondow and Eric Weisstein. "Smarandache Function". MathWorld.
8. V. Seleacu e I. Balacenoiu, The Smarandache Function in Number Theory, Erhus University Press, 1996, ISBN 1-879585-47-2.
9. C. Ashbacher, M.Popescu, An Introduction to the Smarandache Function, Erhus University Press, 1995, ISBN 1-879585-49-9.
10. S. Tabirca, T. Tabirca, K. Reynolds e L.T. Yang, Calculating Smarandache function in parallel, in Parallel and Distributed Computing, 2004. Third International Symposium on Algorithms, Models and Tools for Parallel Computing on Heterogeneous Networks, 2004, pp. 79–82, DOI:10.1109/ISPDC.2004.15.
11. R. Muller, Editorial (PDF), in Smarandache Function Journal, vol. 1, 1990, p. 1, ISBN 84-252-1918-3.
12. Paul Erdős e Ilias Kastanas, The smallest factorial that is a multiple of n (solution to problem 6674) (PDF), in American Mathematical Monthly, vol. 101, 1994, p. 179, DOI:10.2307/2324376..
13. I.Cojocaru, S. Cojocaru, The First Constant of Smarandache (PDF), in Smarandache Notions Journal, vol. 7, 1996, pp. 116–118.
14. I. Cojocaru e S. Cojocaru, The Second Constant of Smarandache (PDF), in Smarandache Notions Journal, vol. 7, 1996, pp. 119–120.
15. I. Cojocaru e S. Cojocaru, The Third and Fourth Constants of Smarandache (PDF), in Smarandache Notions Journal, vol. 7, 1996, pp. 121–126.
16. E. Burton, On Some Series Involving the Smarandache Function (PDF), in Smarandache Function Journal, vol. 6, 1995, pp. 13–15.

Voci correlate

• Fattoriale
• Funzione sigma
• Serie di Kempner

Collegamenti esterni

• (EN) Eric W. Weisstein, Funzione di Kempner, su MathWorld, Wolfram Research.