3
\$\begingroup\$

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.)

\$\endgroup\$
  • 1
    \$\begingroup\$ What counts as "partial" hardcoding? \$\endgroup\$ – Geobits Jan 22 '15 at 17:57
  • 2
    \$\begingroup\$ "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? \$\endgroup\$ – Martin Ender Jan 22 '15 at 17:57
  • \$\begingroup\$ @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. \$\endgroup\$ – randomra Jan 22 '15 at 18:07
  • \$\begingroup\$ @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. \$\endgroup\$ – randomra Jan 22 '15 at 19:54
  • 2
    \$\begingroup\$ For 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. \$\endgroup\$ – xnor Jan 23 '15 at 1:49
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ The byte counter says 314 chars and 451 bytes. \$\endgroup\$ – KSFT Jan 22 '15 at 19:30
  • \$\begingroup\$ @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. \$\endgroup\$ – Martin Ender Jan 22 '15 at 19:33
  • \$\begingroup\$ I did look at the link. It gave the same numbers as copying the code from your answer. It said 314 chars both times. \$\endgroup\$ – KSFT Jan 22 '15 at 19:36
  • \$\begingroup\$ @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. \$\endgroup\$ – Martin Ender Jan 22 '15 at 19:38
  • \$\begingroup\$ 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! \$\endgroup\$ – KSFT Jan 22 '15 at 19:39
5
\$\begingroup\$

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]
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Martin Ender Jan 25 '15 at 23:12
  • \$\begingroup\$ 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 \$\endgroup\$ – Level River St Jan 26 '15 at 0:42
  • \$\begingroup\$ Ruby has a bit-shift operator a<<b, which lets you write a*2**b shorter. \$\endgroup\$ – xnor Jan 29 '15 at 5:37
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.