mersenneforum.org Distributed Nagell-Ljunggren Search
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2014-12-27, 16:59   #23
TeknoHog

Mar 2010
Jyvaskyla, Finland

22·32 Posts

Quote:
 Originally Posted by R. Gerbicz To see your chances for a new solution: Rewrite the equation: x^n=(x-1)*y^q+1. If the abc conjecture is true for K=1/4 and eps=1, then x^n<0.25*rad(x^n*(x-1)*y^q*1)^2=0.25*rad(x*(x-1)*y)^2<0.25*(x^2*y)^2, but it is easy to see that y^q<2*x^(n-1), from this y<2*x^((n-1)/q) is also true. So x^n<0.25*(x^2*2*x^((n-1)/q))^2=x^(4+2*(n-1)/q) n<4+2*(n-1)/q<=4+2*(n-1)/3 as there is no new solution for q=2. And from this we get that n<10, what is also proved that this gives no further solution.
Interesting. This is a little beyond my current knowledge, but I'm not surprised that such problems are interconnected. I guess I better pour my computing resources into ABC@Home instead :)

Quote:
 About the search: it is too slow. If you need to quickly eliminate the q as an exponent for given (x,n) pair I would choose r=k*q+1 prime (where r>x) and check that c=((x^n-1)/(x-1))^k mod r is 1 or not. If it is not then (x^n-1)/(x-1) is not a perfect q-th power. Or to avoid to compute the multiplicative inverse just test if (x^n-1)^k==(x-1)^k mod r is true or not. The probability that this holds is roughly O(1/q), use more r primes and perhaps precalculate them (if you fix x then the set of q primes is the same, I would do this way). With this you can almost completely avoid to use bignums.
Good point, I've also been thinking about various optimizations with Fermat's Little Theorem, this looks nice. I think this needs an extra check in case r|y, but it's still a considerable speedup.

Last fiddled with by TeknoHog on 2014-12-27 at 17:20

2014-12-27, 18:22   #24
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

5FB16 Posts

Quote:
 Originally Posted by TeknoHog Good point, I've also been thinking about various optimizations with Fermat's Little Theorem, this looks nice. I think this needs an extra check in case r|y, but it's still a considerable speedup.
Yes, you are right, but it is still better to check that r|(x^n-1) is true or not. These methods just working, for a recent similar problem see http://www.spoj.com/problems/PRIMPOW2/ this is even a harder problem since there half of the input is a perfect power.

 2015-11-11, 00:55 #25 TeknoHog     Mar 2010 Jyvaskyla, Finland 22·32 Posts It's been a fun exercise, but I'm soon closing down this project as I focus on more math fun such as this. Thanks to the few people who helped out and gave new ideas :)

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post Mickey1 Miscellaneous Math 0 2013-03-03 14:50 poily Msieve 6 2012-12-05 12:45 ixfd64 Lounge 4 2008-11-22 01:59 drakkar67 Prime Sierpinski Project 17 2005-11-19 01:29 adpowers Lounge 10 2004-11-05 01:54

All times are UTC. The time now is 07:31.

Tue Jan 25 07:31:43 UTC 2022 up 186 days, 2 hrs, 0 users, load averages: 1.47, 1.36, 1.15

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔