15
\$\begingroup\$

The divisors of a natural number form a poset under the relation of "a divides b?", \$a | b\$. This challenge is to produce the number, \$C\$, of non-empty chains of such posets for natural numbers, \$N\$.

This is A253249 in the Online Encyclopedia of Integer Sequences.

That may sound complicated, but it's not really, let's look at an...

Example

For \$N=28\$ the divisors are \$\{1, 2, 4, 7, 14, 28\}\$ and the number of non-empty chains is \$C(28) = 31\$. The non-empty chains are these subsets of those divisors:

$$\{1\}, \{2\}, \{4\}, \{7\}, \{14\}, \{28\}$$ $$\{1, 2\}, \{1, 4\}, \{1, 7\}, \{1, 14\}, \{1, 28\}, \{2, 4\},$$ $$\{2, 14\}, \{2, 28\}, \{4, 28\}, \{7, 14\}, \{7, 28\}, \{14, 28\}$$ $$\{1, 2, 4\}, \{1, 2, 14\}, \{1, 2, 28\}, \{1, 4, 28\}, \{1, 7, 14\},$$ $$\{1, 7, 28\}, \{1, 14, 28\}, \{2, 4, 28\}, \{2, 14, 28\}, \{7, 14, 28\},$$ $$\{1, 2, 4, 28\}, \{1, 2, 14, 28\}, \{1, 7, 14, 28\}$$

These chains are those non-empty subsets of \$\{1, 2, 4, 7, 14, 28\}\$ such that all pairs of elements \$\{a, b\}\$ satisfy either \$a|b\$ or \$b|a\$ - that is one is a divisor of the other.

Since \$2\$ does not divide \$7\$ and \$7\$ does not divide \$2\$, no chain has a subset of \$\{2, 7\}\$.

Similarly no chain has a subset of either \$\{4, 7\}\$ or \$\{4, 14\}\$.

Furthermore the empty chain, \$\emptyset = \{\}\$, is not counted.

I/O

You may take input and give output using defaults.
\$N\$ is guaranteed to be a positive integer, \$N \ge 1\$.

Tests

The first \$360\$ values are:

1, 3, 3, 7, 3, 11, 3, 15, 7, 11, 3, 31, 3, 11, 11, 31, 3, 31, 3, 31, 11, 11, 3, 79, 7, 11, 15, 31, 3, 51, 3, 63, 11, 11, 11, 103, 3, 11, 11, 79, 3, 51, 3, 31, 31, 11, 3, 191, 7, 31, 11, 31, 3, 79, 11, 79, 11, 11, 3, 175, 3, 11, 31, 127, 11, 51, 3, 31, 11, 51, 3, 303, 3, 11, 31, 31, 11, 51, 3, 191, 31, 11, 3, 175, 11, 11, 11, 79, 3, 175, 11, 31, 11, 11, 11, 447, 3, 31, 31, 103, 3, 51, 3, 79, 51, 11, 3, 303, 3, 51, 11, 191, 3, 51, 11, 31, 31, 11, 11, 527, 7, 11, 11, 31, 15, 175, 3, 255, 11, 51, 3, 175, 11, 11, 79, 79, 3, 51, 3, 175, 11, 11, 11, 831, 11, 11, 31, 31, 3, 175, 3, 79, 31, 51, 11, 175, 3, 11, 11, 447, 11, 191, 3, 31, 51, 11, 3, 527, 7, 51, 31, 31, 3, 51, 31, 191, 11, 11, 3, 703, 3, 51, 11, 79, 11, 51, 11, 31, 79, 51, 3, 1023, 3, 11, 51, 103, 3, 175, 3, 303, 11, 11, 11, 175, 11, 11, 31, 191, 11, 299, 3, 31, 11, 11, 11, 1007, 11, 11, 11, 175, 11, 51, 3, 447, 103, 11, 3, 175, 3, 51, 51, 79, 3, 175, 11, 31, 11, 51, 3, 1471, 3, 31, 63, 31, 31, 51, 11, 79, 11, 79, 3, 703, 11, 11, 51, 511, 3, 51, 11, 175, 31, 11, 3, 527, 11, 51, 11, 31, 3, 527, 3, 191, 51, 11, 31, 175, 3, 11, 31, 527, 3, 51, 3, 31, 51, 51, 11, 2175, 7, 51, 11, 31, 3, 175, 11, 79, 79, 11, 11, 703, 11, 11, 11, 191, 11, 175, 3, 175, 11, 51, 3, 527, 3, 11, 175, 31, 3, 51, 11, 1023, 11, 51, 11, 831, 31, 11, 11, 79, 11, 299, 3, 31, 31, 11, 11, 1471, 3, 31, 11, 175, 11, 175, 15, 79, 51, 11, 3, 175, 3, 175, 79, 447, 3, 51, 11, 31, 51, 11, 3, 2415

Scoring

This is , so try to make code in as few bytes as possible in your language of choice. Your score is the number of bytes of your program or function.

\$\endgroup\$
0

18 Answers 18

8
\$\begingroup\$

Jelly, 10 9 7 bytes

ÆḌƬFLḤ’

Try it online!

  Ƭ        Loop while unique:
ÆḌ         Recursively vectorizing proper divisors (empty list if 1).
  ƬF       Deep flatten the full history of results,
    L      take the length,
     Ḥ     double (to account for the chains including the original n),
      ’    and decrement (to not double count the trivial chain of just {n}).
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Nice. I had something similar but with an extra Ẏ$ because I’d not taken advantage of ÆḌ vectorising down to the deepest level. \$\endgroup\$ Oct 11, 2023 at 21:32
  • 1
    \$\begingroup\$ Interestingly this is also similar to the Maple solution in the linked OEIS, except that one would be closer to ÆDÆḌƬFL which is the same byte count. \$\endgroup\$ Oct 11, 2023 at 23:05
  • 1
    \$\begingroup\$ @NickKennedy Regarding both of your comments, you might find the edit history amusing :P \$\endgroup\$ Oct 11, 2023 at 23:10
8
\$\begingroup\$

Python 3, 45 bytes

f=lambda n,d=1:d//n or-~f(d)*(n%d<1)+f(n,d+1)

Try it online!

51 bytes

f=lambda n:1+sum(1+f(d)for d in range(1,n)if n%d<1)

Try it online!

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

R, 44 bytes

`?`=\(n,d=1)`if`(d<n,(n?d+1)+(1+?d)*!n%%d,1)

Attempt This Online!

Port of @xnor's Python answer.

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

Nekomata + -n, 6 bytes

ĎSᵉti¦

Attempt This Online!

ĎSᵉti¦
Ď       Divisors
 S      Find a subset such that
  ᵉt      removing the first element
     ¦    is divisible by
    i     removing the last element

-n counts the number of solutions.

\$\endgroup\$
0
5
\$\begingroup\$

05AB1E, 10 bytes

ÑæʒRüÖP}g<

Try it online!

Ñ      # divisors of N
æ      # subsets
ʒ      # keep those such that
 R      # when reversed
 üÖ     # whether each term divides the previous one?
 P      # all
}
g      # and take the length
<      # -1
\$\endgroup\$
5
\$\begingroup\$

Rust, 63 54 bytes

(#2)

Thanks to @att for the massive –9 bytes!

fn f(n:i64)->i64{(1..n).fold(1,|a,d|a-(1>>n%d)*!f(d))}

Attempt This Online!

Rust, 63 bytes

(#0)

Originally based on @xnor's Python answer. Straightforward functional implementation of their idea.

fn f(n:u64)->u64{(1..n).filter(|d|n%d<1).fold(1,|a,d|1+a+f(d))}

Attempt This Online!

Rust, 63 bytes

(#1)

Works just like #0, but the filter is inlined into the fold.

fn f(n:u64)->u64{(1..n).fold(1,|a,d|if n%d<1{1+f(d)}else{0}+a)}

Attempt This Online!

Previous attempts and ideas can be found in the ATO links. It took me a while to realize that the descriptive symbolic idea of using itertools, powerset and so on looks extremely cool but just isn't suited for code golf at all if less readable solutions exist.

They all work the same way, with the exception that the first two functions evaluate recursively lazily and the last one eagerly (Infinite recursion is prevented by not calling the closure when the iterator is empty, providing this as a base case). The performance difference is noticeable. I'm sure there must be a way to golf one of these even further (more likely the latter two than the former). It's quite likely that the golfing potential has now been exhausted.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ fn f(n:i64)->i64{(1..n).fold(1,|a,d|a-(1>>n%d)*!f(d))} \$\endgroup\$
    – att
    Oct 27, 2023 at 23:49
4
\$\begingroup\$

Uiua, 18 bytes

∧+1+1∵(|1↬2)⊚=0◿⇡.

Try it online!

∧+1+1∵(|1↬2)⊚=0◿⇡.  input: a positive integer n
⊚=0◿⇡.   proper divisors of n:
  ◿⇡.       n modulo (each of) range of n
  ⊚=0       indices of zeros
∵(|1↬2)  recurse on each
+1         add 1 to each result
∧+1       sum the results and add 1
\$\endgroup\$
4
\$\begingroup\$

JavaScript (ES6), 35 bytes

-11 bytes thanks to @Neil!

Returns the \$n\$-th term.

f=(n,d=n)=>d--&&f(n,d)-!(n%d)*~f(d)

Try it online!

Or try a faster version (36 bytes) that generates the 360 first values listed in the challenge.

Commented

f = (        // f is a recursive function taking:
  n,         //   n = input
  d = n      //   d = current divisor candidate
) =>         //
d-- &&       // if d is not 0 (decrement it afterwards):
  f(n, d) -  //   do a 1st recursive call with the updated d
  !(n % d) * //   test whether d is a divisor of n
             //   if not, ignore the result of ...
  ~f(d)      //   ... a 2nd recursive call with n = d
             //   (otherwise, increment the final count)
\$\endgroup\$
3
  • 3
    \$\begingroup\$ f=(n,d=n)=>d--&&f(n,d)+(n%d?0:1+f(d)) is both shorter and faster. Ported from my Charcoal answer. \$\endgroup\$
    – Neil
    Oct 11, 2023 at 23:54
  • \$\begingroup\$ f=(n,d=n)=>d--&&f(n,d)-(n%d?0:~f(d)) is a byte shorter. f=(n,d=n)=>d--&&f(n,d)-!(n%d)*~f(d) is a further byte shorter but back to being inefficient. \$\endgroup\$
    – Neil
    Oct 12, 2023 at 6:16
  • \$\begingroup\$ @Neil Ugh. Much better indeed! Thank you. \$\endgroup\$
    – Arnauld
    Oct 12, 2023 at 8:00
4
\$\begingroup\$

JavaScript (Node.js), 37 bytes

f=(n,p=n)=>--p?f(n,p)+!(n%p)*-~f(p):1

Try it online!

Found independent, I'd just leave it here

\$\endgroup\$
2
3
\$\begingroup\$

Retina 0.8.2, 34 bytes

.+
$*
+%M!&`^|(1+$)(?<=^\1\1+)|$
¶

Try it online! Link includes test cases. Explanation:

.+
$*

Convert to unary.

+%M!&`^|(1+$)(?<=^\1\1+)|$

Calculate \$ A253249(i) = 1 + \sum_{j|i} 1 + A253249(j) \$. The +% repeatedly processes inner terms until they become empty. The !& outputs overlapping matches. The (1+$)(?<=^\1\1+) matches factors of \$ i \$, and the leading and trailing empty match applies the two \$ 1 + \$ terms somehow... not quite sure how that works, but I'm not complaining. The result is actually the number of newlines generated by the repeated factorisation.

Convert to decimal.

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 21 bytes

FN⊞υ↨Eι∧¬∧κ﹪ικ⊕§υκ¹Iυ

Try it online! Link is to verbose version of code. Outputs the first \$ n \$ values starting at \$ N=0 \$ whose value is considered to be \$ 0 \$. Explanation: \$ A253249(i) = \sum_{j|i} 1+A253249(j) \$ where \$ 0 \$ is considered to divide any integer.

FN

Loop \$ n \$ times.

⊞υ↨Eι∧¬∧κ﹪ικ⊕§υκ¹

Calculate \$ A253249(i) \$ using the above recurrence relation.

Iυ

Output the results.

22 bytes for a 1-indexed version:

FN⊞υ⊕↨Eι∧¬﹪⊕ι⊕κ⊕§υκ¹Iυ

Try it online! Link is to verbose version of code. Outputs the first \$ n \$ values. Explanation: \$ A253249(i+1) = 1 + \sum_{j+1|i+1} 1+A253249(j+1) \$.

FN

Loop \$ n \$ times.

⊞υ⊕↨Eι∧¬﹪⊕ι⊕κ⊕§υκ¹

Calculate \$ A253249(i+1) \$ using the above recurrence relation.

Iυ

Output the results.

\$\endgroup\$
2
\$\begingroup\$

PARI/GP, 31 bytes

f(n)=sumdiv(n,d,1+if(d<n,f(d)))

Attempt This Online!

\$\endgroup\$
2
\$\begingroup\$

Ruby, 79 38 bytes

f=->n{1+(1...n).sum{|r|1[n%r]*-~f[r]}}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Mathematica, 43 28 bytes

Saved 15 bytes thanks to the comment of @alephalpha


Golfed version. Try it online!

1+Tr[1+#0/@Most@Divisors@#]&

Ungolfed version. Try it online!

f[n_] := f[n] = With[{divisors = Divisors[n]}, Total[(1 + If[# < n, f[#], 0]) & /@ divisors]];
Table[Print[i, " -> ", f[i]], {i, 1, 30}]
\$\endgroup\$
1
  • \$\begingroup\$ 1+Tr[1+#0/@Most@Divisors@#]&. \$\endgroup\$
    – alephalpha
    Oct 13, 2023 at 3:12
2
\$\begingroup\$

Haskell, 38 bytes

f n=1+sum[1+f d|d<-[1..n-1],mod n d<1]

A simple port of @xnor's python answer

Attempt This Online!

\$\endgroup\$
2
\$\begingroup\$

Japt v1.4.5 -x, 15 10 bytes

â à ®ä!v ×

Try it

Thanks to @Shaggy for saving 5 bytes by using an older version of Japt ( improvements specified inside parens )

â       divisors( now sorted )
à       combinations( now without empty combination )
®       map by
ä       map each consecutive pair of a combination 
!v      divisible? ( now with argument swapped by prepending ! to function argument)
×       multiply reduce 

-x flag to output the sum 
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 10 bytes in v1.4.5 \$\endgroup\$
    – Shaggy
    Oct 22, 2023 at 22:10
2
\$\begingroup\$

Desmos, 119 118 bytes

L=[1...n]
D=L[mod(n,L)=0]
d=D.count
F=D[mod(floor(2k/2^{[1...d]}),2)=1]
f(n)=∑_{k=1}^{2^d-1}0^{mod(F[2...],F).total}

Try It On Desmos!

Try It On Desmos! - Prettified

Port of Command Master's answer, so make sure to go upvote that answer as well!

\$\endgroup\$
0
\$\begingroup\$

APL (Dyalog Unicode), 51 45 44 bytes

+/((∘.≤⍨⍳∘⍴)≡0=∘.|⍨)¨¯1↓{,⊃∘.,/⍵,¨⊂⊂⍬}(∪⊢∨⍳)

The index origin is set to 1 (⎕IO←1). The number to be analyzed is entered to the right of the code.

Try it on TryAPL.org!

With credit to ngn's prior challenge answer for the short powerset code segment.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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