प्रोजेक्ट यूलर नंबर 338

Question

मैं प्रोजेक्ट यूलर problem 338 पर फंस गया हूं। यहां मैंने अभी तक किया है ...

चलिए क्रमशः चौड़ाई और ऊंचाई x और y(x,y) के साथ एक आयत को इंगित करते हैं। नए आयत बनाने के लिए आप डी चरणों के साथ विकर्ण के नीचे एक प्रकार की सीढ़ी (जैसा कि समस्या विवरण में दिखाया गया है) काटने पर विचार कर सकते हैं। लेकिन एक नया आयताकार बनाने के लिए निम्नलिखित को पकड़ना होगा: d|x और या तो (d-1)|y या (d+1)|y। नया आयत तब (x/d*(d-1), y/(d-1)*d) या (x/d*(d+1), y/(d+1)*d) बन जाता है। जाहिर है कि नए आयतों का क्षेत्र पुराना आयताकार जैसा ही है।

है कि G(10)=55 और G(1000)=971745 के माध्यम से सभी प्रासंगिक घ पाशन और केवल एक बार (x,y) और (y,x) गिनती करने के लिए एक सेट सावधान किया जा रहा करने के लिए सभी नए आयतों जोड़कर पुष्टि करने के लिए पर्याप्त था।

इस विधि के साथ मुख्य मुद्दा यह है कि दो अलग-अलग तरीकों से एक नया आयत बनाना संभव है। उदाहरण के लिए, (9,8)(6,12) और (12,6) दोनों d=3 और d-1 या d+1y को विभाजित कर सकते हैं। या (4,4) का एक और उदाहरण (2,8) और (8,2) दोनों क्रमश: d=2 और d=1 के साथ बदलता है।

मैं this blog post पढ़ने के लिए पर्याप्त भाग्यशाली था। यह बदले में पक्षों में से एक के लिए खोज करके डुप्लिकेट की जांच करने की आवश्यकता को हटा देता है।

def F(w, h): 
    if w&1 and h&1: return 0 
    if w<h: w,h = h,w 

    r = 0 
    x = 1 
    while x**2 <= w*h: 
     if (w*h)%x!=0 or x==h: 
      x += 1 
      continue 

     if w%(w-x)==0 or x%(x-h)==0: 
      r += 1 

     x += 1 

    return r 

def G(N): 
    s = 0 
    for w in range(1, N+1): 
     for h in range(1, w+1): 
      s += F(w,h) 

    return s 

जी (10) अभी तक भी कितनी तेजी से एफ यह है की परवाह किए बिना हल करने के लिए लंबे समय से की आवश्यकता होगी। मुझे लगता है कि यह आवश्यक है करने के लिए या तो जहां के माध्यम से हम पाश सभी एक्स sieving एल्गोरिथ्म के कुछ प्रकार का उपयोग गिनती कितने (डब्ल्यू, ज) ज < = w < = 10 संतुष्ट, x | (डब्ल्यू * ज) , एक्स! = एच और (डब्ल्यूएक्स) | डब्ल्यू या (एक्सएच) | एक्स।

मुझे लगता है कि एक ओ (एन ^2/3) एल्गोरिदम संभव होना चाहिए ... लेकिन मैं यहां फंस गया हूं!

---

संपादित: के बाद से मैं इसे हल करने में असमर्थ हूँ मैं मंच के लिए उपयोग नहीं है। यही कारण है कि मैं मदद मांग रहा हूँ। मैंने अन्य प्रश्नों को पूरा कर लिया है और से निपटना चाहते हैं यह प्रश्न अब!

संपादित करें 2: मुझे लगता है कि प्रमुख कारकों के क्षेत्रों पर विचार करना एक मृत अंत है। ऐसा इसलिए है क्योंकि 10 विभिन्न क्षेत्रों हैं। प्राइम क्षेत्रों के साथ आयताकारों में 0 समाधान होते हैं, सेमीफाइम क्षेत्रों के साथ आयतों में 1 समाधान होता है यदि प्राइम में से एक 2 होता है अन्यथा उनके पास 0 समाधान होते हैं। लेकिन अकेले सभी सेमिप्रिम समाधानों की गिनती बहुत लंबी होगी क्योंकि हमें सभी प्राइम्स पी को गिनने की आवश्यकता होगी जैसे कि 2 * पी जो संभव नहीं है।

संपादित 3:

def G(N): 
    s = 0 
    for x in range(1, N): 
     for h in range(1, N+1): 
      if x==h: continue 
      for w in range(max(h, x**2//h), N+1): 
       if (w*h)%x==0 and x%(w-x)==0 and x%(x-h)==0: 
        s -= 1 

    for x in range(1, N): 
     for h in range(1, N+1): 
      if x==h: continue 
      for w in range(max(h, x**2//h), N+1): 
       if (w*h)%x==0 and w%(w-x)==0: 
        s += 1 

    for x in range(1, N): 
     for h in range(1, N+1): 
      if x==h: continue 
      for w in range(max(h, x**2//h), N+1): 
       if (w*h)%x==0 and h%(x-h)==0: 
        s += 1 

    return s 

मैं हालांकि काम करेंगे नीचे जानवर बल कोड तोड़ने नहीं लगता कि: मैं कोड नीचे छीन लिया है। याद रखें कि यह पर्याप्त है कि हम इन तीन उपप्रोबम्स में से प्रत्येक को समाधान (एक्स, डब्ल्यू, एच) की गिनती करते हैं। ! क और xh | पिछली बार ऐसा योग की कमी 0 < एक्स < एन, 0 < ज < एन 1, एक्स = ज, अधिकतम (ज, एक्स/घंटा) < डब्ल्यू < एन 1, एक्स के लिए होता है | एच।

मुझे लगता है कि हमें इस धारणा से शुरुआत करनी चाहिए कि कुछ प्राइम पी एक्स, डब्ल्यू, एच या यहां तक ​​कि एक्स-एच को विभाजित करते हैं और फिर देखते हैं कि हम अन्य चर के बारे में क्या कर सकते हैं। यदि यह अच्छी तरह से काम करता है, तो शायद मनमानी के लिए पी ^के पर विचार करें।

Answer 1

मेरे पास अभी तक कोई समाधान नहीं है, लेकिन पाइथन के लिए कुछ दिलचस्प है। मुझे एहसास हुआ कि पाइथन को एल्गोरिदम के संकेत के लिए सुविधाजनक उपकरण के रूप में उपयोग किया जा सकता है! असल में मैंने आपके जैसा एक कार्यक्रम लिखा और प्रोग्राम को तार्किक रूप से बदलना शुरू कर दिया जो परिणाम अपरिवर्तित छोड़ देता है। मैं

def order(x,y): 
    if x>=y: 
     return (x,y) 
    else: 
     return (y,x) 

N=1000 
num=set() 
for n in range(1, N+1): 
    for a in range(1,N//n+1): 
     for b in range(1,N//(n+1)+1): 
      if a==b: continue 
      num.add((order(a*n,b*(n+1)), order(b*n,a*(n+1)))) 

print(N, len(num)) 

जाहिर जानवर बल या यहाँ तक कि एक साधारण पाश 10 से अधिक^12 संभव नहीं है के साथ आया था, लेकिन शायद इस एल्गोरिथ्म के साथ एक कुछ बिंदु पर एक बंद फार्म अभिव्यक्ति पा सकते हैं। यदि यह संख्या के सेट चरित्र के लिए नहीं था, तो यह करने योग्य होगा। हो सकता है कि कोई इस तरह डुप्लिकेट पॉइंट पा सके।

यह एक मृत अंत हो सकता है, लेकिन फिर भी यह बहुत अच्छा है कि अजगर अंकन के लिए इस्तेमाल किया जा सकता और एल्गोरिदम :)

तुम्हारी तरफ किसी भी प्रगति के साथ काम है?