19
\$\begingroup\$

Four integer sequences

In this challenge, you will test four different properties of a positive integer, given by the following sequences. A positive integer N is

  1. perfect (OEIS A000396), if the sum of proper divisors of N equals N. The sequence begins with 6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 2305843008139952128...
  2. refactorable (OEIS A033950), if the number of divisors of N is a divisor of N. The sequence begins with 1, 2, 8, 9, 12, 18, 24, 36, 40, 56, 60, 72, 80, 84, 88, 96, 104, 108, 128...
  3. practical (OEIS A005153), if every integer 1 ≤ K ≤ N is a sum of some distinct divisors of N. The sequence begins with 1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 28, 30, 32, 36, 40, 42, 48, 54, 56...
  4. highly composite (OEIS A002128), if every number 1 ≤ K < N has strictly fewer divisors than N. The sequence begins with 1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040...

Four programs

Your task is to write four programs (meaning full programs, function definitions or anonymous functions that perform I/O by any of the standard methods). Each program shall solve the membership problem of one of these sequences. In other words, each program will take a positive integer N ≥ 1 as input, and output a truthy value if N is in the sequence, and a falsy value if not. You can assume that N is within the bounds of the standard integer type of your programming language.

The programs must be related in the following way. There are four strings ABCD such that

  1. AC is the program that recognizes perfect numbers.
  2. AD is the program that recognizes refactorable numbers.
  3. BC is the program that recognizes practical numbers.
  4. BD is the program that recognizes highly composite numbers.

Scoring

Your score is the total length (in bytes) of the strings ABCD, or in other words, the total byte count of the four programs divided by two. The lowest score in each programming language is the winner. Standard rules apply.

For example, if the four strings are a{, b{n, +n} and =n}?, then the four programs are a{+n}, a{=n}?, b{n+n} and b{n=n}?, and the score is 2+3+3+4=12.

\$\endgroup\$
6
\$\begingroup\$

JavaScript (ES6), 46 + 55 + 6 + 36 = 282 274 ... 158 143 bytes

A:

n=>(r=0,D=x=>x&&D(x-1,n%x||(r++?q-=x:q=n)))(n)

B:

n=>(q=(g=D=x=>x&&!(n%x||(g|=m>2*(m=x),0))+D(x-1))(m=n))

C:

?!g:!q

D:

?(P=k=>--k?D(n=k)<q&P(k):1)(n):n%r<1

The result is 4 anonymous functions which give truthy/falsy values for their respective inputs (AC, AD, and BC give true/false, BD gives 1/0).

Test snippet

let AC =
n=>(r=0,D=x=>x&&D(x-1,n%x||(r++?q-=x:q=n)))(n)
?!g:!q

let AD =
n=>(r=0,D=x=>x&&D(x-1,n%x||(r++?q-=x:q=n)))(n)
?(P=k=>--k?D(n=k)<q&P(k):1)(n):n%r<1

let BC =
n=>(q=(g=D=x=>x&&!(n%x||(g|=m>2*(m=x),0))+D(x-1))(m=n))
?!g:!q

let BD =
n=>(q=(g=D=x=>x&&!(n%x||(g|=m>2*(m=x),0))+D(x-1))(m=n))
?(P=k=>--k?D(n=k)<q&P(k):1)(n):n%r<1

let update = n => O.innerText = [
  'perfect: ' + AC(n),
  'refactorable: ' + AD(n),
  'practical: ' + BC(n),
  'highly composite: ' + BD(n)
].join("\n")
<input type=number value=1 min=1 oninput=update(this.value)>
<pre id=O></pre>

\$\endgroup\$
  • 1
    \$\begingroup\$ I like how you have spread the actual code over all 4 parts and mixed it with the "conditionals" unlike me (I have the code on parts A and B and "conditionals" on parts C and D.) \$\endgroup\$ – Erik the Outgolfer Mar 17 '18 at 15:55
2
\$\begingroup\$

Jelly, 8 + 17 + 2 1 + 2 = 29 28 bytes

A:

Æṣ⁼$Ædḍ$

B:

ÆDŒPS€QṢwRµṖÆdṀ<Ʋ

C:

ƭ

D:

0?

For practical numbers (BC), 0 is falsy and any other result is truthy.

AC and BC are full programs, since they're not reusable as functions.

\$\endgroup\$
  • \$\begingroup\$ BC and BD don't seem to work properly. \$\endgroup\$ – Jonathan Allan Mar 17 '18 at 23:25
  • \$\begingroup\$ ÆDŒPS€ḟ@RṆµṖÆd<ÆdẠµ works as B for a cost of two bytes though (and makes BC return 0 and 1 only like the others). \$\endgroup\$ – Jonathan Allan Mar 17 '18 at 23:41
  • \$\begingroup\$ @JonathanAllan Oh no, it seems that I confused ŒP with ŒṖ. What a shame! Does it work if you fix that? (i.e. try my new edit) It's not that it's very easy to test anyway, that's why I haven't included a TIO link yet. \$\endgroup\$ – Erik the Outgolfer Mar 18 '18 at 9:24
0
\$\begingroup\$

Haskell, 69 + 133 + 3 + 3 = score 208

A:

d n=filter((<1).mod n)[1..n]
f n=[sum(d n)-n==n,length(d n)`elem`d n]

B:

import Data.List
d n=filter((<1).mod n)[1..n]
f n=[all(\n->any(==n)$sum$subsequences$d n)[1..n],all((<length(d n)).length.d)[1..n-1]]

C:

!!0

D:

!!1

Try it online!

Yeah, it's pretty cheap but I'm not smart enough for a cooler solution. :P

\$\endgroup\$
  • 1
    \$\begingroup\$ I don't know much about Haskell but this could help you with subsequences \$\endgroup\$ – Asone Tuhid Mar 18 '18 at 17:13
  • \$\begingroup\$ [x|x<-[1..n],mod n x<1] is shorter than filter((<1).mod n)[1..n]. \$\endgroup\$ – Laikoni Mar 18 '18 at 23:11

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.