केम्पनर फंक्शन

केम्पनर फ़ंक्शन का ग्राफ़

संख्या सिद्धांत में, केम्पनर फ़ंक्शन $S(n)$ किसी दिए गए धनात्मक पूर्णांक के लिए परिभाषित किया गया है $n$ सबसे छोटी संख्या होना $s$ ऐसा है कि $n$ को विभाजित करता है factorial $s!$. उदाहरण के लिए, संख्या $8$ विभाजित नहीं करता $1!$, $2!$, or $3!$, लेकिन करता है divide $4!$, so $S(8)=4$.

इस फ़ंक्शन की विशेषता यह है कि इसमें अत्यधिक असंगत एसिम्प्टोटिक विश्लेषण होता है: यह अभाज्य संख्याओं पर रैखिक कार्य करता है लेकिन केवल फैक्टोरियल संख्याओं पर लघुगणकीय वृद्धि बढ़ाता है।

इतिहास

इस फ़ंक्शन पर सबसे पहले 1883 में फ़्राँस्वा एडौर्ड अनातोले लुकास द्वारा विचार किया गया था, इसके बाद 1887 में जोसेफ जीन-बैप्टिस्ट न्यूबर्ग आए। 1918 में, ऑब्रे जे. केम्पनर|ए. जे. केम्पनर ने इसके लिए पहला सही एल्गोरिथम दिया computing $S(n)$.

फ्लोरेंटिन स्मारांडचे द्वारा फ़ंक्शन की पुनः खोज के बाद केम्पनर फ़ंक्शन को कभी-कभी स्मरैंडचे फ़ंक्शन भी कहा जाता है in 1980.

गुण

तब से $n$ divides $n!$, $S(n)$ हमेशा पर है most $S(n)$. एक संख्या $n$ 4 से अधिक एक अभाज्य संख्या है यदि और केवल if $S(n)=n$.अर्थात् संख्याएँ $n$ जिसके लिए $S(n)$ के सापेक्ष जितना संभव हो उतना बड़ा है $n$ अभाज्य हैं. दूसरी दिशा में, जिसके लिए संख्याएँ $S(n)$ भाज्य जितना संभव हो उतना छोटा है: $S(k!)=k$, के लिए all $k\geq 1$.

$S(n)$ पूर्णांक गुणांक वाले एक बहुपद के बहुपद की सबसे छोटी संभव डिग्री है, जिसके पूर्णांकों पर सभी मान विभाज्य हैं by $n$. उदाहरण के लिए, तथ्य यह है कि $S(6)=3$ इसका मतलब है कि एक घन बहुपद है जिसके सभी मान शून्य हैं मॉड्यूलर अंकगणित 6, उदाहरण के लिए बहुपद

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

लेकिन यह कि सभी द्विघात या रैखिक बहुपद (अग्रणी गुणांक एक के साथ) कुछ पूर्णांकों पर गैर-शून्य मॉड्यूलो 6 हैं।

अमेरिकी गणितीय मासिक में 1991 में स्थापित और 1994 में हल की गई उन्नत समस्याओं में से एक में, पॉल एर्डोस ने बताया कि फ़ंक्शन $S(n)$ के सबसे बड़े अभाज्य गुणनखंड से मेल खाता है $n$ लगभग सभी के लिए $n$ (इस अर्थ में कि अपवादों के सेट का स्पर्शोन्मुख घनत्व शून्य है)।

कम्प्यूटेशनल जटिलता

केम्पनर समारोह $S(n)$ एक मनमानी संख्या का $n$ प्रधान शक्तियों से अधिक, अधिकतम है $p^{e}$ डिवाइडिंग $n$, का $S(p^{e})$.कब $n$ स्वयं एक प्रमुख शक्ति है $p^{e}$, इसके केम्पनर फ़ंक्शन को बहुपद समय में गुणकों को क्रमिक रूप से स्कैन करके पाया जा सकता है $p$ जब तक पहला व्यक्ति न मिल जाए जिसके भाज्य में पर्याप्त गुणज हों of $p$. समान कलन विधि को किसी के लिए भी बढ़ाया जा सकता है $n$ जिसका अभाज्य गुणनखंडन पहले से ही ज्ञात है, इसे गुणनखंडन में प्रत्येक अभाज्य शक्ति पर अलग से लागू करके और उस एक को चुनना जो सबसे बड़े मूल्य की ओर ले जाता है।

फॉर्म के एक नंबर के लिए $n=px$, कहाँ $p$ प्रधान है और $x$ मै रुक जाना $p$, केम्पनर फ़ंक्शन $n$ है $p$.इससे यह पता चलता है कि सेमीप्राइम (दो प्राइम का उत्पाद) के केम्पनर फ़ंक्शन की गणना करना कम्प्यूटेशनल रूप से इसके मुख्य गुणनखंड प्रक्रिया को खोजने के बराबर है, जिसे एक कठिन समस्या माना जाता है। अधिक सामान्यतः, जब भी $n$ एक भाज्य संख्या है, जिसका सबसे बड़ा सामान्य भाजक है $S(n)$ and $n$ आवश्यक रूप से एक गैरतुच्छ भाजक होगा of $n$, अनुमति देना $n$ केम्पनर फ़ंक्शन के बार-बार मूल्यांकन द्वारा कारक बनाया जाना। इसलिए, केम्पनर फ़ंक्शन की गणना करना सामान्यतः मिश्रित संख्याओं का गुणनखंड करने से आसान नहीं हो सकता है।

सन्दर्भ और नोट्स

This article incorporates material from Smarandache function on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.