Funcția Kempner

Graficul funcției Kempner

În teoria numerelor , funcția Kempner $S(n)$ ${\ displaystyle S (n)}$ ${\ displaystyle S (n)}$ ^[1] este definit pentru un număr natural dat $n$ ${\ displaystyle n}$ $n$ ca cel mai mic număr $s$ ${\ displaystyle s}$ $s$ astfel încât $n$ ${\ displaystyle n}$ $n$ împarte factorialul $s!$ ${\ displaystyle s!}$ ${\ displaystyle s!}$ . ^[2] De exemplu, numărul $8$ ${\ displaystyle 8}$ $8$ nu împarte $1!$ ${\ displaystyle 1!}$ ${\ displaystyle 1!}$ , $2!$ ${\ displaystyle 2!}$ ${\ displaystyle 2!}$ , $3!$ ${\ displaystyle 3!}$ ${\ displaystyle 3!}$ , dar este un divizor al $4!$ ${\ displaystyle 4!}$ ${\ displaystyle 4!}$ , asa de $S(8)=4$ ${\ displaystyle S (8) = 4}$ ${\ displaystyle S (8) = 4}$ . Această funcție are proprietatea de a crește liniar pe numerele prime, dar mai puțin decât logaritmic pe numerele factoriale.

Istorie

Această funcție a fost luată în considerare pentru prima dată de François Édouard Anatole Lucas în 1883, ^[3] urmat de Joseph JB Neuberg în 1887. ^[4] În 1918, AJ Kempner a furnizat primul algoritm de calcul $S(n)$ ${\ displaystyle S (n)}$ ${\ displaystyle S (n)}$ . ^[5] Florentin Smarandache a redescoperit-o în 1980 ^[6] , motiv pentru care este uneori numită „funcția Smarandache”. ^[7] ^[8] ^[9] ^[10]

Proprietate

De cand $n$ ${\ displaystyle n}$ $n$ împarte $n!$ ${\ displaystyle n!}$ $n!$ , valoarea a $S(n)$ ${\ displaystyle S (n)}$ ${\ displaystyle S (n)}$ este cel mult $n$ ${\ displaystyle n}$ $n$ . Un număr $n>4$ ${\ displaystyle n> 4}$ $n> 4$ este un număr prim dacă și numai dacă $S(n)=n$ ${\ displaystyle S (n) = n}$ ${\ displaystyle S (n) = n}$ . ^[11] Adică numerele $n$ ${\ displaystyle n}$ $n$ pentru care $S(n)$ ${\ displaystyle S (n)}$ ${\ displaystyle S (n)}$ este cea mai mare posibilă în raport cu $n$ ${\ displaystyle n}$ $n$ sunt numerele prime. Pe de altă parte, numerele pentru care $S(n)$ ${\ displaystyle S (n)}$ ${\ displaystyle S (n)}$ este cel mai mic posibil sunt factorialele: $S(k!)=k$ ${\ displaystyle S (k!) = k}$ ${\ displaystyle S (k!) = k}$ , pentru fiecare $k\geq 1$ ${\ displaystyle k \ geq 1}$ $k \ geq 1$ .

$S(n)$ ${\ displaystyle S (n)}$ ${\ displaystyle S (n)}$ este cel mai mic grad posibil al unui polinom monic cu coeficienți întregi astfel încât valorile asumate pe numerele întregi să fie toate divizibile cu $n$ ${\ displaystyle n}$ $n$ . ^[1] De exemplu, faptul că $S(6)=3$ ${\ displaystyle S (6) = 3}$ ${\ displaystyle S (6) = 3}$ înseamnă că există un polinom cub ale cărui valori sunt zero modulo 6, cum ar fi

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

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

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

dar că toate polinoamele pătratice și liniare (cu coeficientul de direcție egal cu 1) sunt diferite de 0 modul 6 pentru un număr întreg.

Într-una dintre problemele avansate ale American Mathematical Monthly , propusă în 1991 și rezolvată în 1994, Paul Erdős a observat că funcția $S(n)$ ${\ displaystyle S (n)}$ ${\ displaystyle S (n)}$ coincide cu cel mai mare factor prim al $n$ ${\ displaystyle n}$ $n$ pentru „aproape toți” numerele întregi (în sensul că densitatea asimptotică a setului de excepții este zero). ^[12]

Complexitatea computațională

Funcția Kempner $S(n)$ ${\ displaystyle S (n)}$ ${\ displaystyle S (n)}$ pentru un număr arbitrar $n$ ${\ displaystyle n}$ $n$ este maximul de $S(p^{e})$ ${\ displaystyle S (p ^ {e})}$ ${\ displaystyle S (p ^ {e})}$ , cu $p^{e}$ ${\ displaystyle p ^ {e}}$ ${\ displaystyle p ^ {e}}$ primele puteri care împart $n$ ${\ displaystyle n}$ $n$ . ^[5] Unde $n$ ${\ displaystyle n}$ $n$ este ea însăși o putere primară $p^{e}$ ${\ displaystyle p ^ {e}}$ ${\ displaystyle p ^ {e}}$ , funcția sa Kempner în timp polinomial poate fi găsită analizând secvențial multipli de $p$ ${\ displaystyle p}$ $p$ până când cel mai mic este găsit astfel încât factorialul său să conțină destui multipli de $p$ ${\ displaystyle p}$ $p$ . Același algoritm poate fi extins la fiecare $n$ ${\ displaystyle n}$ $n$ a cărei factorizare este cunoscută, aplicând-o separat fiecărei puteri mai întâi în factorizare și alegând cea care duce la cea mai mare valoare.

Pentru un număr în formă $n=px$ ${\ displaystyle n = px}$ ${\ displaystyle n = px}$ , unde este $p$ ${\ displaystyle p}$ $p$ este prim și $X$ ${\ displaystyle x}$ $X$ e mai puțin decât $p$ ${\ displaystyle p}$ $p$ , funcția Kempner a $n$ ${\ displaystyle n}$ $n$ își asumă valoarea $p$ ${\ displaystyle p}$ $p$ . ^[5] Rezultă că calcularea funcției Kempner pentru un număr semiprimă (un produs de două numere prime) este echivalent din punct de vedere computerizat cu găsirea factorizării sale prime, care în acest moment pare a fi o problemă complexă. Mai general, de fiecare dată $n$ ${\ displaystyle n}$ $n$ este un număr compus , cel mai mare divizor comun al $S(n)$ ${\ displaystyle S (n)}$ ${\ displaystyle S (n)}$ Și $n$ ${\ displaystyle n}$ $n$ va fi un divizor non-banal al $n$ ${\ displaystyle n}$ $n$ , permițând factorizarea $n$ ${\ displaystyle n}$ $n$ prin evaluări repetate ale funcției Kempner. Prin urmare, calcularea funcției kempner nu poate fi, în general, mai simplă decât luarea în considerare a unui număr compus.

Serii asociate

Multe serii construite din $S(n)$ ${\ displaystyle S (n)}$ ${\ displaystyle S (n)}$ s-a dovedit a fi convergent. ^[13] ^[14] ^[15] ^[16] În cazul $S(n)$ ${\ displaystyle S (n)}$ ${\ displaystyle S (n)}$ , în literatura de specialitate, seriile sunt denumite constante Smarandache , chiar și atunci când acestea depind de parametrii auxiliari. Rețineți, de asemenea, că acestea diferă de constantele Smarandache care derivă din generalizarea lui a conjecturii andriciene . Următoarele sunt exemple de astfel de serii:

$\sum _{n=2}^{\infty }{\frac {1}{S(n)!}}=1,09317\ldots$ ${\ displaystyle \ sum _ {n = 2} ^ {\ infty} {\ frac {1} {S (n)!}} = 1,09317 \ ldots}$ ${\ displaystyle \ sum _ {n = 2} ^ {\ infty} {\ frac {1} {S (n)!}} = 1,09317 \ ldots}$ OEIS: A048799 .
$\sum _{n=2}^{\infty }{\frac {S(n)}{n!}}=1,71400629359162\ldots$ ${\ displaystyle \ sum _ {n = 2} ^ {\ infty} {\ frac {S (n)} {n!}} = 1.71400629359162 \ ldots}$ ${\ displaystyle \ sum _ {n = 2} ^ {\ infty} {\ frac {S (n)} {n!}} = 1.71400629359162 \ ldots}$ OEIS: A048834 și este irațional .
$\sum _{n=2}^{\infty }{\frac {1}{\prod _{i=2}^{n}S(i)}}=0,719960700043\ldots$ ${\ displaystyle \ sum _ {n = 2} ^ {\ infty} {\ frac {1} {\ prod _ {i = 2} ^ {n} S (i)}} = 0.719960700043 \ ldots}$ ${\ displaystyle \ sum _ {n = 2} ^ {\ infty} {\ frac {1} {\ prod _ {i = 2} ^ {n} S (i)}} = 0.719960700043 \ ldots}$ OEIS: A048835 .
$\sum _{n}S(n)^{-\alpha }{S(n)!}^{-1/2}<\infty ,\,{\text{ con }}\alpha >1.$ ${\ displaystyle \ sum _ {n} S (n) ^ {- \ alpha} {S (n)!} ^ {- 1/2} <\ infty, \, {\ text {cu}} \ alpha> 1 .}$ ${\ displaystyle \ sum _ {n} S (n) ^ {- \ alpha} {S (n)!} ^ {- 1/2} <\ infty, \, {\ text {cu}} \ alpha> 1 .}$

Notă

^ ^a ^b Numit „numere Kempner” în Enciclopedia on-line a secvențelor întregi : vezi Sloane, NJA (ed.). "Secvența A002034 (numerele Kempner: cel mai mic număr m astfel încât n împarte m!)" . Enciclopedia on-line a secvențelor întregi. Fundația OEIS
^ "Funcția Smarandache" , PlanetMath
^ E. Lucas , Întrebarea Nr. 288 , în Mathesis , vol. 3, 1883, p. 232.
^ J. Neuberg, Solutions de questions proposées, Question Nr. 288 , în Mathesis , vol. 7, 1887, pp. 68-69.
^ ^a ^b ^c AJ Kempner, Diverse , în American Mathematical Monthly , vol. 25, nr. 5, 1918, pp. 201 -210, DOI : 10.2307 / 2972639 , JSTOR 2972639 .
^ F. Smarandache, O funcție în teoria numerelor , în An. Univ. Timișoara, Ser. Sf. Mat. , vol. 18, 1980, pp. 79–88 , MR 0619740 , arXiv : math / 0405143 .
^ Jonathan Sondow și Eric Weisstein. "Funcția Smarandache" . MathWorld .
^ V. Seleacu și I. Balacenoiu, Funcția Smarandache în teoria numerelor , Erhus University Press, 1996, ISBN 1-879585-47-2 .
^ C. Ashbacher, M. Popescu, An Introduction to the Smarandache Function , Erhus University Press, 1995, ISBN 1-879585-49-9 .
^ S. Tabirca, T. Tabirca, K. Reynolds and LT Yang, Calculating Smarandache function in parallel , in Parallel and Distributed Computing, 2004. Al treilea simpozion internațional privind algoritmi, modele și instrumente pentru calcul paralel pe rețele heterogene , 2004, pp. 79-82, DOI : 10.1109 / ISPDC.2004.15 .
^ R. Muller, Editorial ( PDF ), în Smarandache Function Journal , vol. 1, 1990, p. 1, ISBN 84-252-1918-3 .
^ Paul Erdős și Ilias Kastanas, Cel mai mic factorial care este multiplu de n (soluție la problema 6674) ( PDF ), în American Mathematical Monthly , vol. 101, 1994, p. 179, DOI : 10.2307 / 2324376 . .
^ I. Cojocaru, S. Cojocaru, The First Constant of Smarandache ( PDF ), in Smarandache Notions Journal , vol. 7, 1996, pp. 116–118.
^ I. Cojocaru și S. Cojocaru, A doua constantă a lui Smarandache ( PDF ), în Smarandache Notions Journal , vol. 7, 1996, pp. 119-120.
^ I. Cojocaru și S. Cojocaru, A treia și a patra constantă a Smarandache ( PDF ), în Smarandache Notions Journal , vol. 7, 1996, pp. 121–126.
^ E. Burton, Pe unele serii care implică funcția Smarandache ( PDF ), în Smarandache Function Journal , vol. 6, 1995, pp. 13-15.

Elemente conexe

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[oeis-1] Numit „numere Kempner” în Enciclopedia on-line a secvențelor întregi : vezi Sloane, NJA (ed.). "Secvența A002034 (numerele Kempner: cel mai mic număr m astfel încât n împarte m!)" . Enciclopedia on-line a secvențelor întregi. Fundația OEIS

[2] "Funcția Smarandache" , PlanetMath

[history1-3] E. Lucas , Întrebarea Nr. 288 , în Mathesis , vol. 3, 1883, p. 232.

[history2-4] J. Neuberg, Solutions de questions proposées, Question Nr. 288 , în Mathesis , vol. 7, 1887, pp. 68-69.

[history3-5] AJ Kempner, Diverse , în American Mathematical Monthly , vol. 25, nr. 5, 1918, pp. 201 -210, DOI : 10.2307 / 2972639 , JSTOR 2972639 .

[history4-6] F. Smarandache, O funcție în teoria numerelor , în An. Univ. Timișoara, Ser. Sf. Mat. , vol. 18, 1980, pp. 79–88 , MR 0619740 , arXiv : math / 0405143 .

[7] Jonathan Sondow și Eric Weisstein. "Funcția Smarandache" . MathWorld .

[smf1-8] V. Seleacu și I. Balacenoiu, Funcția Smarandache în teoria numerelor , Erhus University Press, 1996, ISBN 1-879585-47-2 .

[smf2-9] C. Ashbacher, M. Popescu, An Introduction to the Smarandache Function , Erhus University Press, 1995, ISBN 1-879585-49-9 .

[smf3-10] S. Tabirca, T. Tabirca, K. Reynolds and LT Yang, Calculating Smarandache function in parallel , in Parallel and Distributed Computing, 2004. Al treilea simpozion internațional privind algoritmi, modele și instrumente pentru calcul paralel pe rețele heterogene , 2004, pp. 79-82, DOI : 10.1109 / ISPDC.2004.15 .

[11] R. Muller, Editorial ( PDF ), în Smarandache Function Journal , vol. 1, 1990, p. 1, ISBN 84-252-1918-3 .

[12] Paul Erdős și Ilias Kastanas, Cel mai mic factorial care este multiplu de n (soluție la problema 6674) ( PDF ), în 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 și S. Cojocaru, A doua constantă a lui Smarandache ( PDF ), în Smarandache Notions Journal , vol. 7, 1996, pp. 119-120.

[15] I. Cojocaru și S. Cojocaru, A treia și a patra constantă a Smarandache ( PDF ), în Smarandache Notions Journal , vol. 7, 1996, pp. 121–126.

[16] E. Burton, Pe unele serii care implică funcția Smarandache ( PDF ), în Smarandache Function Journal , vol. 6, 1995, pp. 13-15.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]