Generate all 4-perfect numbers

3

1

Your program or function should output all the 36 4-perfect numbers in increasing order separated by newlines.

An n positive integer is a k-perfect number (multiply perfect number) if the sum of its divisors including itself (i.e. the sigma function of n) equals k*n.

For example 120 is a 3-perfect number because 1 + 2 + 3 + 4 + 5 + 6 + 8 + 10 + 12 + 15 + 20 + 24 + 30 + 40 + 60 + 120 = 360 = 3*120.

Details

  • Your entry should actually produce the output and terminate on your machine before you submit your answer. (i.e. the program should terminate in a reasonable time)
  • Hardcoding is allowed.
  • Built-in functions or data closely related to the problem (e.g. sigma function) are disallowed.
  • This is code-golf but as the task is non-trivial without major hardcoding non-golfed entries are welcomed too.

(This is a great detailed page about the history of all multiply perfect numbers.)

randomra

Posted 2015-01-22T17:53:29.323

Reputation: 19 909

1What counts as "partial" hardcoding? – Geobits – 2015-01-22T17:57:26.530

2"Your entry should actually produce the output on your machine not just in theory." In what time frame? Furthermore, what functions are closely related? Is Divisors[n] closely related? Is Divisible[m,n] closely related? Is Mod[m,n] closely related? – Martin Ender – 2015-01-22T17:57:44.863

@MartinBüttner No time frame. Non of those are closely related. The purpose of that rule is to disallow simple one-liners available in some languages. @Geobits Removed partial. – randomra – 2015-01-22T18:07:20.550

@MartinBüttner I don't know how else can I say that if you had seen the output appear on your screen than you can post the program because it actually produced the output not just theoretically. – randomra – 2015-01-22T19:54:47.557

2For those of you trying to get started, here's some structure I noticed: The numbers tend to have many small prime factors, and the large prime factors are all one less than a product of smaller prime factors in the factorization. For example, the largest number 1598455815964665104598224777343146075218771968 is divisible by 2^37, its largest prime factor 524287 is 2^19-1, and its second-largest prime factor 174763 = 4*43691 - 1, where 43691 is its third-largest prime factor. – xnor – 2015-01-23T01:49:02.133

Answers

3

CJam, 377 bytes

All the characters are part of extended ASCII, so I'm counting this as a single byte per character

"Ò|+^ø¥©~öôxõÕÊïB.X}Ã+ç
âà©¥;ØÓé@ä¦qØH®üzGOwCàæ/Â$ªh#þ>üJNDÂTR{^Ìý±OáÉÚ6ï®I?Çvqf³e1é^¶­[Y½5ãþ#_-__xF'IMØ*¬È6Vô+§mâ?µTJÉ9$·Ùöµ¨±Dac&¼'h,q÷ZwÎE^§Å{åÁûà\µ;óÛ¤{n'ÜGÐÓR!³¥èè>(~\"NbU*ötmù¦ªUe|Rñ¾!a9TYÇ&êë½ôâ··¨JÆ­#Ù&îCÎÍð4q<­ÌÏïj;Åd*òz(x    ?ßâ%d8ƬÔUÎ=¶îÖÀ+mHH9â\"=PʱedèËU·  /þr<ÆGR;|úÀ趡õrì@öÆ"255bBbAa/N*

I'm sure Stack Exchange will have swallowed some of the characters, so you might want to copy the code from this pastebin.

Test it here.

This solution is purely hardcoded. It interprets the code points of the characters as the digits of a base-255 number, gets the base-11 digits of that, splits on the digit 10 and joins the resulting arrays by newlines.

Martin Ender

Posted 2015-01-22T17:53:29.323

Reputation: 184 808

The byte counter says 314 chars and 451 bytes. – KSFT – 2015-01-22T19:30:50.123

@KSFT As I said in the answer, don't copy the code from my answer, because Stack Exchange strips unprintable characters. Use the link in my answer instead, which should show all 377 characters. Furthermore, that site counts bytes in UTF-8, but it's not necessary to encode the input in UTF-8 since all characters are in extended ASCII, so one only needs a single byte to encode each character. – Martin Ender – 2015-01-22T19:33:12.510

I did look at the link. It gave the same numbers as copying the code from your answer. It said 314 chars both times. – KSFT – 2015-01-22T19:36:46.287

@KSFT Hm, the link does work for me. Did you copy it in first, and then use the link? In some browsers, the permalinks don't work and are overridden by whatever you last opened in the counter. – Martin Ender – 2015-01-22T19:38:33.383

Huh...that is weird... I typed something else in the counter, then opened the link in a new tab, and it had what I had typed instead of your code! – KSFT – 2015-01-22T19:39:54.703

@KSFT Lesson learned, replaced it with a pastebin link. – Martin Ender – 2015-01-22T19:42:08.463

5

Prime factorization (Ruby ,570 542 bytes)

Rev 0

Below is a table of the prime factorizations of the 36 required numbers (copied from Wolfram, hopefully with no errors.) Only 31 prime factors are involved if I have counted correctly, and some of these always occur together, for example 137*547*1093 and 683*2731*8191.

It should be possible to condense the information in the table, or perhaps even employ a search strategy. This should beat simply compressing the numbers.

Unfortunately the numbers are too big even for a 128-bit integer, which means I can't use C. Ruby and Python do support arbitrary precision integers. I have put the table in valid Ruby syntax, which makes it my first ever Ruby program! 

puts 2**5  *3**3  *5    *7
puts 2**3  *3**2  *5    *7           *13
puts 2**2  *3**2  *5    *7**2        *13      *19
puts 2**9  *3**3  *5          *11                         *31   
puts 2**7  *3**3  *5**2                  *17              *31
puts 2**9  *3**2        *7    *11    *13                  *31
puts 2**8  *3     *5    *7                    *19             *37       *73
puts 2**10 *3**3  *5**2                               *23 *31                 *89
puts 2**13 *3**3  *5          *11                                 *43                 *127
puts 2**14 *3     *5    *7                    *19         *31                                   *151
puts 2**13 *3**2        *7    *11    *13                          *43                 *127
puts 2**5  *3**4        *7**2 *11**2          *19**2                                  *127
puts 2**8  *3**2        *7**2        *13      *19**2          *37       *73           *127
puts 2**7  *3**10 *5                     *17          *23                        *107                                               *3851   
puts 2**7  *3**6  *5                     *17          *23                                  *137           *547           *1093
puts 2**14 *3**2        *7**2        *13      *19**2      *31                         *127      *151
puts 2**5  *3**4        *7**2 *11**2          *19**4                                            *151                *911
puts 2**9  *3**4        *7    *11**3                      *31**2     *61    *83                      *331
puts 2**8  *3**2        *7**2        *13      *19**4            *37     *73                     *151                *911
puts 2**25 *3**3  *5**2                       *19         *31                                                  *683            *2731       *8191
puts 2**17 *3**10       *7                    *19**2  *23       *37     *73      *107 *127                                           *3851
puts 2**17 *3**6        *7                    *19**2  *23       *37     *73           *127 *137           *547           *1093
puts 2**25 *3**4        *7    *11**2          *19**2                                  *127                     *683            *2731       *8191
puts 2**25 *3**5        *7**2        *13      *19**2                                  *127                     *683            *2731       *8191
puts 2**17 *3**10       *7                    *19**4  *23       *37     *73      *107           *151                *911             *3851
puts 2**25 *3**10 *5                          *19     *23                        *107                          *683            *2731 *3851 *8191
puts 2**17 *3**6        *7                    *19**4  *23       *37     *73                *137 *151      *547      *911 *1093
puts 2**25 *3**6  *5                          *19     *23                                  *137           *547 *683      *1093 *2731       *8191
puts 2**25 *3**4        *7    *11**2          *19**4                                            *151           *683 *911       *2731       *8191
puts 2**25 *3**5        *7**2        *13      *19**4                                            *151           *683 *911       *2731       *8191
puts 2**33 *3**4        *7    *11**3                      *31        *61    *83                      *331                                        *43691 *131071
puts 2**33 *3**10       *7    *11                     *23                   *83  *107                *331                      *3851             *43691 *131071
puts 2**33 *3**6        *7    *11                     *23                   *83            *137      *331 *547           *1093                   *43691 *131071
puts 2**37 *3**4        *7    *11**3                      *31        *61    *83                      *331                                        *43691        *174763*524287
puts 2**37 *3**10       *7    *11                     *23                   *83  *107                *331                      *3851             *43691        *174763*524287
puts 2**37 *3**6        *7    *11                     *23                   *83            *137      *331 *547           *1093                   *43691        *174763*524287

Rev 1 Just starting to gather some terms.

#683*2731*8191=15278451143, 137*547*1093=81908327, 107*3851=412057, 174763*524287=91625968981, 19**2*151*911=49659521, 83*331=27473, 11**3*31*61=2516921,37*73=2701,19*19=361

puts 2**5  *3**3  *5       *7
puts 2**3  *3**2  *5       *7           *13
puts 2**2  *3**2  *5       *7**2        *13      *19
puts 2**9  *3**3  *5             *11                         *31    
puts 2**7  *3**3  *5**2                     *17              *31
puts 2**9  *3**2           *7    *11    *13                  *31
puts 2**8  *3     *5       *7                    *19                *2701
puts 2**10 *3**3  *5**2                                  *23 *31                 *89
puts 2**13 *3**3  *5             *11                                 *43                 *127
puts 2**14 *3     *5       *7                    *19         *31                               *151
puts 2**13 *3**2           *7    *11    *13                          *43                 *127
puts 2**5  *3**4           *7**2 *11**2          *19**2                                  *127
puts 2**8  *3**2           *7**2        *13      *19**2            *2701                 *127
puts 2**7  *3**10 *5                        *17          *23                                                                           *412057  
puts 2**7  *3**6  *5                        *17          *23                                                                *81908327
puts 2**14 *3**2           *7**2        *13      *19**2      *31                         *127  *151
puts 2**5  *3**4           *7**2 *11**2          *19**2                                            *49659521
puts 2**9  *3**4           *7                                *31    *2516921  *27473
puts 2**8  *3**2           *7**2        *13      *19**2            *2701                           *49659521
puts 2**25 *3**3  *5**2                          *19         *31                                                            *15278451143
puts 2**17 *3**10          *7                    *19**2  *23       *2701                 *127                                           *412057
puts 2**17 *3**6           *7                    *19**2  *23       *2701                 *127                               *81908327
puts 2**25 *3**4           *7    *11**2          *19**2                                  *127                                                   *15278451143
puts 2**25 *3**5           *7**2        *13      *19**2                                  *127                                                   *15278451143
puts 2**17 *3**10          *7                    *19**2  *23       *2701                           *49659521                            *412057
puts 2**25 *3**10 *5                             *19     *23                                                                            *412057 *15278451143
puts 2**17 *3**6           *7                    *19**2  *23       *2701                           *49659521                *81908327
puts 2**25 *3**6  *5                             *19     *23                                                                *81908327           *15278451143
puts 2**25 *3**4           *7    *11**2          *19**2                                            *49659521                                    *15278451143
puts 2**25 *3**5           *7**2        *13      *19**2                                            *49659521                                    *15278451143
puts 2**33 *3**4           *7                                       *2516921   *27473                                                               *43691 *131071
puts 2**33 *3**10          *7    *11                     *23                   *27473                                             *412057           *43691 *131071
puts 2**33 *3**6           *7    *11                     *23                   *27473                                       *81908327               *43691 *131071
puts 2**37 *3**4           *7                                       *2516921   *27473                                                               *43691        *91625968981
puts 2**37 *3**10          *7    *11                     *23                   *27473                                             *412057           *43691        *91625968981
puts 2**37 *3**6           *7    *11                     *23                   *27473                                       *81908327               *43691        *91625968981

Rev 2, 570 542 bytes (thanks to Martin for the improvement)

As this is my first Ruby program, I just stuck with the simple approach of continuing to gather terms. Compression of the numbers would be great if anyone knows how to do that.

I could save a few more bytes by evaluating some of the literal-only expressions in the variable assignment part, but I decided to leave them for clarity.

e=361
f=e*e*137561
g=27473
h=2516921
j=2701
k=81908327*729
m=412057*59049
n=15278451143*2**25
p=g*43691*2**33*7
q=131071
r=91625968981*16
s=127
t=1024
w=250240
x=1467648
y=7439488
puts [30240,32760,2178540,23569920,45532800,142990848,510720*j,t*42833475,t*510840*s,t*149417520,t*3099096*s,15367968*e*s,x*e*j*s,w*m,w*k,t*429378768*e*s,15367968*f,8999424*g*h,x*j*f,n*397575,t*m*y*j*s,t*k*y*j*s,n*68607*e*s,n*154791*e*s,t*20608*j*f*m,2185*n*m,t*20608*j*f*k,2185*k*n,68607*f*n,154791*f*n,81*h*p*q,253*p*m*q,253*p*k*q,81*h*p*r,253*p*m*r,253*p*k*r]

Level River St

Posted 2015-01-22T17:53:29.323

Reputation: 22 049

no need for all that assignment to z and the for loop at the end. simply put the puts right in front of that array (and I don't think you'll need a space after the puts in that case). you should be able to save a few more bytes, by e.g. assigning j when it's first used, like ...,510720*j=2701,.... and I think a few more if you give 253*p a name. – Martin Ender – 2015-01-25T23:12:38.350

Thanks @MartinBüttner, I had assumed that puts [1,2,3] would not insert a newline after each number, but it seems it does, at least in interactive mode on my PC (but not on the Ruby website.) I will edit that in later. I reckon with a bit of effort it should be possible to get close to 500 bytes with this type of program, but I'm not that interested in pushing it further right now. When I know more Ruby I'd like to use some kind of compression as well as taking advantage of the prime factorisation. Or you could post an answer and show me how it's done :-D – Level River St – 2015-01-26T00:42:42.933

Ruby has a bit-shift operator a<<b, which lets you write a*2**b shorter. – xnor – 2015-01-29T05:37:11.500

1

Perl, 629 bytes

(Not counting one line break added for legibility)

use bignum;$_="762K7FF8G213DECG167A6O2B6C68K885DEO5238CFOA36590COF77C22S239FB8CS5DD688ASA40BF4CBEKA54B500277O15A1AA76D5D18K3515C82E18268K479DC3635ACS3D2C86DAC7F142K8A2CE47EB04E2O3DA39DD49D1B489O2B29246D35B6E2_34983A6E0D56A03116W8112111C1388B007CAW535DB1D8191384C3E_BC1718A816B9CA38E_139CE2CE0C2A6520D7D64EAW1580287D7C721FC8E0EFE_30219245E63381BDAD34236W34C38D4A316E11A76BA62_1F166FEDE2AA3B8DEE71C2_4623D01AD5164B207D6A72_5F16A2BFB16257500DB6g2BCF9FAD6C4DE65CA22F8C6Eg6B83D96C6A0809DCDEC5BFF2g3F648C3210B25B8737B940492k1D3523B8D99B8761B6AFBE903D97Ak47AD5F744AA0CC4A843901F8DEAA6k";
s#(\w+?)([G-z])#print hex($1)<<(ord($2)-71),$/#ge

The numbers are hard-coded in hexadecimal with a bit of compression applied to the trailing zeroes.

Try it out here.

r3mainer

Posted 2015-01-22T17:53:29.323

Reputation: 19 135

Asked: 2015-01-22T17:53:29.323

Viewed: 855 times

Active: 2015-01-28T23:03:35.620