दिए गए नंबर के लिए लगातार चार संख्याएं खोजें

Question

मान लीजिए कि एक निश्चित संख्या है तो हमें परीक्षण करना चाहिए यदि यह लगातार चार संख्याओं का उत्पाद है?

तो y हमारी दी गई संख्या है तो हमें y = x(x+1)(x+2)(x+3) किसी भी मनमाने ढंग से x के लिए परीक्षण करना चाहिए?

इस समस्या के लिए एल्गोरिदम कैसे डिज़ाइन करें?

मैं इसे इस तरह किया है:

import java.util.*; 

public class Product 
{ 
    public static int product(int i) 
    { 
     return i * (i+1) * (i+2) * (i+3); 
    } 

    public static void main(String[] args) 
    { 
     Scanner scnr = new Scanner(System.in); 
     int x = scnr.nextInt(); 
     for (int i = 0; i < x/2; i++) 
     { 
      if (product(i) == x) 
      { 
       System.out.println("number is product of 4 consecutive numbers"); 
       break; 
      } 
     } 
    } 
} 

Answer 1

साथ

y = x(x+1)(x+2)(x+3) = x^4 + 6x^3 + 11x^2 + 6x 

सूचना है कि गुणांक लगभग सममित देखने के शुरू, लेकिन वहाँ अंत में कोई 1 है।

ताकि

y = z^2 - 1 

अर्थात लगता है

z^2 = x^4 + 6x^3 + 11x^2 + 6x + 1 

एक्स 4 की सभी शक्तियों के गुणांकों हैं, और x^0 x^4 में से उन लोगों और 1 हैं, इसलिए हम x^1 के गुणांक है, जो हम कहते हैं a खोजने की जरूरत है:

z = (x^2 + ax + 1)^2 = x^4 + 2ax^3 + (2+a^2)x^2 + 2ax + 1 

x^1 के गुणांक तुलना, x^2, या x^3 a = 3

(समीकरणों से ऊपर की आवश्यकता नहीं है कि एक्स के किसी भी, वाई या जेड एक पूर्णांक है देता है, लेकिन संभवतः खो देंगे जटिल या नकारात्मक जड़ों में हमें कोई दिलचस्पी नहीं है)

तो हम x के लिए एक द्विघात का समाधान कर सकते हैं:

x^2 + 3x + 1 - sqrt(y+1) = 0 

देता

x = -3 +/- sqrt(9 - 4 * (1-sqrt(y+1))) 
    --------------------------------- 
       2 

    = -3 +/- sqrt(5 + 4 sqrt(y+1)) 
    ---------------------------- 
       2 

जो एक पूर्णांक हो सकता है अगर sqrt(y+1) एक पूर्ण वर्ग z है, और (5+4z) भी एक पूर्ण वर्ग है (यदि z है एक पूर्णांक, 5-4z अजीब है, इसलिए इसका वर्ग रूट, यदि एक पूर्णांक भी अजीब है और x एक पूर्णांक होगा)।

तो परीक्षण करें कि z = sqrt(y+1) एक पूर्णांक है, फिर परीक्षण करें कि 5+4z एक पूर्ण वर्ग है।

Answer 2

संपादित: (अगर यह लगातार चार पूर्णांकों का एक उत्पाद नहीं है एक त्वरित तरीका परीक्षण करने के लिए) प्रश्न को गलत तरीके से पढ़ते हैं, लेकिन क्या इसके लायक है के लिए:

perfect square की तुलना में लगातार चार पूर्णांक का कोई भी उत्पाद equal to one less है।

Answer 3

मैं 'वाई' की चौथी जड़ प्राप्त करके शुरू करूंगा। यह आपको y (यानी 'x') के सबसे छोटे कारक के लिए अनुमान लगाएगा जिसका आप उपयोग कर सकते हैं। इसे मानक कारककरण एल्गोरिदम के आधार के रूप में उपयोग करें।

Answer 4

संख्या के बहुत सारे के लिए हम आसानी से अगर वे एक निश्चित एक्स या नहीं फिट हो सकता है देख सकते हैं:

• वाई, 3 से भाज्य होना चाहिए के बाद से लगातार संख्या के कम से कम एक 3
द्वारा भाज्य होना चाहिए
• वाई, 4 से भाज्य होना चाहिए के बाद से लगातार संख्या के कम से कम एक 4

द्वारा भाज्य होना चाहिए तो Y 12 तक कम से कम भाज्य होना चाहिए (3 * 4)। इसका मतलब है कि आप आसानी से सभी संख्याओं का लगभग 92% निकाल सकते हैं।

चूंकि वाई के मान में कम से कम 4-वें शक्ति होगी, तो आप 4 के रूट (या आप इसे अंग्रेजी में कैसे कहते हैं) ले कर शुरू कर सकते हैं, फिर इसे पूर्णांक मान, इसे एक्स को कॉल करना और एक्स (एक्स + 1) (एक्स + 2) (एक्स + 3) के परिणाम की गणना करना।

परिणाम शायद अधिक होगा (क्योंकि हमने एक्स जैसे अन्य कारकों को एक्स, 2 की शक्ति के लिए एक्स, ...) छोड़ दिया है।

अब एक्स से 1 घटाएं और समान गणनाएं करें।

जब तक परिणाम वाई तुलना में अधिक है, यह दोहराते रहें जब तक परिणाम में कम है, या आप वास्तव में वाई प्राप्त

Answer 5

आपका समीकरण

के रूप में सरल किया जा सकता

y = x^4 + 6*x^3 + 11*x^2 + 6x 

आप एक्स से शुरू कर सकते हैं = 1 और जांच के लिए ऊपर जाओ। हम एक बहुत ही आसान-गणना-गणना ऊपरी सीमा को नोट कर सकते हैं: y की चौथी जड़ (या y के वर्ग रूट की वर्ग जड़)। मतलब, जब आप उस नंबर तक पहुंचते हैं, तो आप रुक सकते हैं। यह आपके लिए भाग्यशाली है, क्योंकि सौभाग्य से हमारे लिए, चौथी जड़ें बहुत बहुत छोटी हैं।

10,000 तक की संख्या के लिए, यह जांचना बहुत आसान है, क्योंकि आप अधिकतम दस पूर्णांक जांचने जा रहे हैं। यदि आपकी संख्या 500 से कम है, तो आपको केवल चार पूर्णांक जांचने की आवश्यकता होगी।

1,000,000+ पर, आपको 31 और अधिक संख्याओं की जांच शुरू करनी होगी, इसलिए यह कम मामूली हो सकता है।

---

ऊपरी और निचली सीमा

के बाद कुछ सावधान शोधन Wolfram Alpha के कारण, दो बातें यह निष्कर्ष निकाला गया है:

1. एक अधिक परिष्कृत ऊपरी y के लिए बाध्य^0.25 - 1.2
2. एक वाई^0.25 - 1.5

की निश्चित निचली सीमा ...

y = num_to_check 
k = Math.sqrt(Math.sqrt(y)) # or Math.pow(y,0.25) 
lower = int(k-1.5) 
upper = int(Math.ceil(k-1.2)) 
for n in (lower...upper) 
    if n * (n+1) * (n+2) * (n+3) == y 
    return n 
    end 
end 
return nil 

ध्यान दें कि इस मामले में, वहाँ दो संख्या का एक अधिकतम कर रहे हैं किसी भी y के लिए जांच की जानी।

संपादित करें: एक्स को केवल पूर्णांक को परिष्कृत करने के बाद, ऐसा लगता है कि सभी मामलों में जांच करने के लिए केवल एक संख्या है, क्योंकि आपकी सीमा एक संख्या तक कम हो जाती है। ठंडा! (ब्रायन के लिए धन्यवाद)

Answer 6

y की चौथी जड़ की गणना करें, इसे नीचे घुमाएं और इसे a पर कॉल करें। a(a-1)(a-2)(a-3)y से बहुत कम है। y की चौथी जड़ की गणना करें, इसे गोल करें, और इसे b पर कॉल करें। b(b+1)(b+2)(b+3)y से अधिक है। अब आपके पास से शुरू करने के लिए तीन संभावित संख्याएं हैं: a-2, a-1 और a (नोट a = b या a = b-1)। तो यह (a-2)(a-1)a(a+1), (a-1)a(a+1)(a+2) और a(a+1)(a+2)(a+3) जांचने के लिए पर्याप्त होना चाहिए।

Answer 7

आपको केवल floor(y**(0.25)-1) का परीक्षण करने की आवश्यकता है। जैसे ही वाई अनंतता तक पहुंचता है, एक्स y**0.25-1.5 (नीचे से) तक पहुंचता है।

कुछ हद तक, यह बल्कि सहज है। x*(x+1)*(x+2)*(x+3) चार संख्याओं का एक उत्पाद है जिसका औसत x+1.5 के बराबर है। जब एक्स ऊंचा होता है, 1.5 छोटा दिखता है।

Answer 8

उत्तर बहुत आसान है।
दिए गए नंबर वाई के लिए यदि y + 1 सही वर्ग नहीं है तो y लगातार चार संख्याओं का उत्पाद नहीं है। यदि वाई + 1 सही वर्ग है तो y लगातार चार संख्याओं का उत्पाद होता है यदि केवल और यदि sqrt (5 + 4 * sqrt (y + 1)) पूर्णांक है।

Answer 9

जैसा कि अन्य ने कहा है, वाई की चौथी जड़ से शुरू करें (चलिए इसे z कहते हैं)।

अनुक्रम x, x + 1, ... x + 3 में से, हम जानते हैं कि कुछ मान ज़ेड से कम होना चाहिए, और कुछ z से अधिक होना चाहिए (क्योंकि वे सभी z के बराबर नहीं हो सकते हैं)।

तो, हम जानते हैं कि

x <= ceiling(z) 
x+3 >= floor(z) 

कि आप संख्या का एक बहुत छोटा सीमा देता है एक्स के लिए प्रयास करने के लिए।