zxv12
|
  |
| Joined: 18 Jul 2009 |
| Total Posts: 286 |
|
|
| 05 Jul 2012 03:33 PM |
Hurro.
I've been finding perfect numbers lately (ok, just today, but stick with me, k?).
Is this a good algorithm?
local HighestFound = 0; local NumberFound = 0; local n = 0; local mf = math.floor; local A = 0 local c = os.clock;
while true do
n = n + 1;
if n%2 == 0 then for i = 1, n-1 do if n%i == 0 then A = A + i; end; end; end;
if A == n then HighestFound = n; NumberFound = NumberFound + 1; print("\n\n\nHighest perfect number found: "..HighestFound.."\n Number of perfect numbers found: "..NumberFound.."\n CPU time elasped: "..c()); end;
A = 0;
end;
Also, have any of you ever attempted to find perfect numbers? If so, how many have you found, which language, and how did you calculate them?
I'll be looking forward to your replies! |
|
|
| Report Abuse |
|
|
Trioxide
|
  |
| Joined: 29 Mar 2011 |
| Total Posts: 32902 |
|
| |
|
zxv12
|
  |
| Joined: 18 Jul 2009 |
| Total Posts: 286 |
|
|
| 05 Jul 2012 03:53 PM |
I've also written a perfect number finder in Python, but I don't know if it's faster or slower yet.
Same algorithm.
n = 1 a = 0 h = 0 f = 0 i = 1
while True: n += 1 if n%2 != 1: while True: if n%i == 0: a += i if a > n or i >= n-1: break i += 1 if a == n: f += 1 h = n i = 1 a = 0 if n >= 496: break
print("Highest perfect found: "+str(h)+" Number of perfects found: "+str(f))
(Unfortunetly you won't be able to use it unless you intend it yourself. Blame John for crappy forums.) |
|
|
| Report Abuse |
|
|
|
| 05 Jul 2012 04:53 PM |
| Factorization is NP hard. No algorithm will scale well. |
|
|
| Report Abuse |
|
|
|
| 05 Jul 2012 04:58 PM |
Actually, primality is much easier. And 2^(p−1)(2^p−1) when 2^p - 1 is prime is an even Perfect number. But these are not all of the perfect numbers, just apparently most of them (at least for small numbers).
|
|
|
| Report Abuse |
|
|
HotThoth
|
  |
 |
| Joined: 24 Aug 2010 |
| Total Posts: 1176 |
|
|
| 05 Jul 2012 07:36 PM |
@BlueTaslem: I believe that's the case for every even perfect number, and maybe every perfect number (no odd perfect numbers have yet been found). So every known perfect number is of that form, and every number of that form is an even perfect number.
@OP: The algorithm you have will miss odd perfect numbers, if there are any. And if you're just looking for even perfect numbers, probably easier to just increment i by 2 each time and not have a i%2==0 check.
- HotThoth |
|
|
| Report Abuse |
|
|
HotThoth
|
  |
 |
| Joined: 24 Aug 2010 |
| Total Posts: 1176 |
|
|
| 05 Jul 2012 07:37 PM |
And fun fact, if we ever get quantum computers, apparently factoring goes from being hard to being not-so-hard.
- HotThoth |
|
|
| Report Abuse |
|
|
Combrad
|
  |
| Joined: 18 Jul 2009 |
| Total Posts: 11025 |
|
|
| 06 Jul 2012 07:59 AM |
local n = 0 for i = 1,100 do n=n+1 print(2^(n−1)(2^n−1)) end
? pretty sure mine does thte same |
|
|
| Report Abuse |
|
|
|
| 06 Jul 2012 09:08 AM |
wiki says dem (even) purfect numbers are liek n 1's followed by n-1 0's (or was it n+1)
idc wat n was tho.
liek
1110000
k |
|
|
| Report Abuse |
|
|
zxv12
|
  |
| Joined: 18 Jul 2009 |
| Total Posts: 286 |
|
|
| 06 Jul 2012 09:30 AM |
There are no odd perfect numbers.
All perfect numbers are also "Ore's harmonic numbers", and there are no odd Ore's harmonic numbers other than 1.
I'll try the prime method. |
|
|
| Report Abuse |
|
|
SN0X
|
  |
| Joined: 24 Oct 2011 |
| Total Posts: 7277 |
|
|
| 06 Jul 2012 10:45 AM |
Yay I'm unbanned :D
(I was zxv12.)
And I don't get the prime method. When I tried it, it seemed to just spew out random numbers. |
|
|
| Report Abuse |
|
|
|
| 06 Jul 2012 11:21 AM |
| Another fun fact, they've come out with a program for quantum computers already. |
|
|
| Report Abuse |
|
|
SN0X
|
  |
| Joined: 24 Oct 2011 |
| Total Posts: 7277 |
|
|
| 06 Jul 2012 11:51 AM |
Why would finding factors be easier using a quantum computer?
Also, why not just harvest a criminal with a life sentance to jail's brain? :P |
|
|
| Report Abuse |
|
|
SN0X
|
  |
| Joined: 24 Oct 2011 |
| Total Posts: 7277 |
|
|
| 06 Jul 2012 11:53 AM |
| "Sorry Jim, I forgot to feed my computer yesterday and now it's dead." |
|
|
| Report Abuse |
|
|
HotThoth
|
  |
 |
| Joined: 24 Aug 2010 |
| Total Posts: 1176 |
|
|
| 06 Jul 2012 02:02 PM |
@SN0X: We don't know that. There are no *known* perfect odd numbers. But we haven't proved that there aren't any. It may be the case that there just aren't any until you get past 10^100000 (this has indeed happened before).
And yeah, true story, it's actually polytime with a quantum computer. Pretty crazy, right? I'm sure wikipedia has a better explanation than I could give of that theorem.
@Combrad: Those will not all be perfect numbers, because that's not necessarily a prime you're starting with; the primality is a necessary condition for even perfect numbers.
- HotThoth |
|
|
| Report Abuse |
|
|
Combrad
|
  |
| Joined: 18 Jul 2009 |
| Total Posts: 11025 |
|
|
| 06 Jul 2012 02:05 PM |
I overlooked that, trying to complete a 3D model of a two hectare area is very disctracting.
Can't be asked to write a new one though. |
|
|
| Report Abuse |
|
|
Merely
|
  |
| Joined: 07 Dec 2010 |
| Total Posts: 17266 |
|
|
| 06 Jul 2012 02:05 PM |
| ^ computer science major above? |
|
|
| Report Abuse |
|
|
Combrad
|
  |
| Joined: 18 Jul 2009 |
| Total Posts: 11025 |
|
|
| 06 Jul 2012 02:07 PM |
Actually. Landscape Architecture =D |
|
|
| Report Abuse |
|
|
Merely
|
  |
| Joined: 07 Dec 2010 |
| Total Posts: 17266 |
|
|
| 06 Jul 2012 02:07 PM |
| I late-posted I was pointing at HotThoth lol |
|
|
| Report Abuse |
|
|
Merely
|
  |
| Joined: 07 Dec 2010 |
| Total Posts: 17266 |
|
|
| 06 Jul 2012 02:08 PM |
> factoring will be easy for computers
well there goes RSA encryption... |
|
|
| Report Abuse |
|
|
Combrad
|
  |
| Joined: 18 Jul 2009 |
| Total Posts: 11025 |
|
|
| 06 Jul 2012 02:08 PM |
Close enough. I appreciate the late post. |
|
|
| Report Abuse |
|
|
SN0X
|
  |
| Joined: 24 Oct 2011 |
| Total Posts: 7277 |
|
|
| 06 Jul 2012 02:20 PM |
Late posts are infuriating.
And yes- perfect numbers might only appear after a certain number, or they might be ultra rare. |
|
|
| Report Abuse |
|
|
HotThoth
|
  |
 |
| Joined: 24 Aug 2010 |
| Total Posts: 1176 |
|
|
| 06 Jul 2012 04:08 PM |
@Merely's late-post: Nop. Not originally :P @Merely's later, but not late-post: Pretty much. Soon we may all have to switch to some crazy hyperbolic geometry-based encryption scheme or something that sounds equally cool. |
|
|
| Report Abuse |
|
|
lombardo2
|
  |
| Joined: 30 Nov 2008 |
| Total Posts: 1604 |
|
|
| 06 Jul 2012 05:58 PM |
| Oh right, like the shor's algorithm. We already have quantum computers. |
|
|
| Report Abuse |
|
|
nightname
|
  |
| Joined: 10 Jun 2008 |
| Total Posts: 8960 |
|
|
| 06 Jul 2012 06:16 PM |
"We already have quantum computers."
Technically, we also have teleportation, yet it is not available to everyone. Things which are commercial are not usually considered as "out". We all know Google uses quantum computers - but only they can afford to pay a few millions on a single computer, and they have more than one. |
|
|
| Report Abuse |
|
|