22
\$\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\$
7
\$\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>

| improve this answer | |
\$\endgroup\$
  • 2
    \$\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
3
\$\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.

| improve this answer | |
\$\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
1
\$\begingroup\$

05AB1E, 8 + 16 + 1 + 0 = 25 bytes

A: ѨO©QI®Ö
B: ÑæOILåPILÑ€gRć‹P
C: s
D: 

The long parts each calculate both values, s swaps to the first one.

Ñ          # push list of divisors
 ©         # store this list
  ¨        # remove the last (largest) value
   O       # take the sum
    Q      # is this equal to the input (perfect)
     I     # push the input
      ®    # push the stored divisor list
       g   # take the length
        Ö  # does it divide the input? (refactorable)
        (s)# (swap to perfect)

Try perfect online! or Try refactorable online!

ÑæOILåP    # practical?
Ñ          # push list of divisors
 æ         # take the powerset
  O        # sum of each subset
   IL      # push the range [1..input]
     å     # is each value in the sums of divisor-subsets?
      P    # take the product / boolean all

ILÑ€gRć‹P  # highly composite?
IL         # push the range [1..input]
  Ñ        # take the divisors of each integer
   €g      # take the length of each divisor list
     R     # reverse it (swap the input's to the front)
      ć    # push the first value seperately
       ‹   # is this larger
        P  # than all other values?

(s)        # (swap to practical)

Try practical online! or Try highly composite online

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

Jelly, 5 + 17 + 3 + 3 = 28 bytes

There's already a 28-byte Jelly answer, but I have a different approach, so why not add it too?

Parts

The pilcrow represents a newline.

A: S=¶ḍ¶ (5 bytes)
B: ŒP§iⱮḶ}Ạ¶>ḶÆd$}Ạ¶ (17 bytes)
C: ÆḌñ (3 bytes)
D: Ædç (3 bytes)

Perfect (8 bytes)

S=
ḍ
ÆḌñ

Try it online!

Explanation

S=   Auxiliary dyadic link
S    Sum of items in left argument
 =   Equals right argument?

ḍ   Ignored

ÆḌñ   Main monadic link
ÆḌ    Proper divisors
  ñ   Apply next link, with the number as right argument

Refactorable (8 bytes)

S=
ḍ
Ædç

Try it online!

Explanation

S=   Ignored

ḍ   Auxiliary dyadic link: Divides?

Ædç   Main monadic link
Æd    Number of divisors
  ç   Apply previous link, with the number as right argument

Practical (20 bytes)

ŒP§iⱮḶ}Ạ
>ḶÆd$}Ạ
ÆḌñ

Try it online!

Explanation

ŒP§iⱮḶ}Ạ   Auxiliary dyadic link
ŒP         Power set
  §        Sum of each
   iⱮ      Find index of each item from
     Ḷ}      Lowered range [0..(right argument - 1)]
       Ạ   All?

>ḶÆd$}Ạ   Ignored

ÆḌñ   Main monadic link
ÆḌ    Proper divisors
  ñ   Apply next link, with the number as right argument

Highly composite (20 bytes)

ŒP§iⱮḶ}Ạ
>ḶÆd$}Ạ
Ædç

Try it online!

Explanation

ŒP§iⱮḶ}Ạ   Ignored

>ḶÆd$}Ạ   Auxiliary dyadic link
>         Greater than?
    $     (
 Ḷ   }      Lowered range [0..(right argument - 1)]
  Æd        Number of divisors [of each]
    $     )
      Ạ   All?

Ædç   Main monadic link
Æd    Number of divisors
  ç   Apply previous link, with the number as right argument
| improve this answer | |
\$\endgroup\$
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

| improve this answer | |
\$\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.