Divisor chain counts (1 3 3 7 ...)

Question

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 sequence 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 code-golf, 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.

Unrelated String · Accepted Answer · 2023-10-11 19:45:14Z

8

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

edited Oct 11 at 19:45

answered Oct 11 at 19:18

Unrelated String

21.2k3 gold badges28 silver badges54 bronze badges

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\$
– Nick Kennedy
Oct 11 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\$
– Nick Kennedy
Oct 11 at 23:05
1

\$\begingroup\$ @NickKennedy Regarding both of your comments, you might find the edit history amusing :P \$\endgroup\$
– Unrelated String
Oct 11 at 23:10

Add a comment |

xnor · Accepted Answer · 2023-10-12 00:46:03Z

8

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!

answered Oct 12 at 0:46

xnor

144k26 gold badges273 silver badges637 bronze badges

Add a comment |

pajonk · Accepted Answer · 2023-10-12 06:17:24Z

6

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.

answered Oct 12 at 6:17

pajonk

15.1k3 gold badges21 silver badges65 bronze badges

Add a comment |

alephalpha · Accepted Answer · 2023-10-12 07:48:56Z

6

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.

edited Oct 12 at 7:48

answered Oct 12 at 0:08

alephalpha

46.5k7 gold badges61 silver badges172 bronze badges

Add a comment |

Command Master · Accepted Answer · 2023-10-11 20:13:34Z

5

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

answered Oct 11 at 20:13

Command Master

9,6921 gold badge10 silver badges67 bronze badges

Add a comment |

leo848 · Accepted Answer · 2023-10-28 16:15:30Z

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.

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

Bubbler · Accepted Answer · 2023-10-12 07:52:02Z

4

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

answered Oct 12 at 7:52

Bubbler

73.8k5 gold badges142 silver badges443 bronze badges

Add a comment |

Arnauld · Accepted Answer · 2023-10-12 07:55:58Z

4

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)

edited Oct 12 at 7:55

answered Oct 11 at 20:36

Arnauld

188k20 gold badges171 silver badges631 bronze badges

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 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 at 6:16
\$\begingroup\$ @Neil Ugh. Much better indeed! Thank you. \$\endgroup\$
– Arnauld
Oct 12 at 8:00

Add a comment |

l4m2 · Accepted Answer · 2023-10-12 08:17:41Z

4

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

edited Oct 12 at 8:17

answered Oct 12 at 2:44

l4m2

20.5k2 gold badges19 silver badges85 bronze badges

1

\$\begingroup\$ f=(n,p=n)=>p&&f(n,--p)-!(n%p)*~f(p) \$\endgroup\$
– tsh
Oct 12 at 5:31
\$\begingroup\$ @tsh Rolled back as Arnauld applied it earlier \$\endgroup\$
– l4m2
Oct 12 at 8:18

Add a comment |

Neil · Accepted Answer · 2023-10-12 10:41:43Z

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.

Neil · Accepted Answer · 2023-10-11 23:49:05Z

Charcoal, 21 bytes

ＦＮ⊞υ↨Ｅι∧¬∧κ﹪ικ⊕§υκ¹Ｉυ

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.

ＦＮ

Loop \$ n \$ times.

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

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

Ｉυ

Output the results.

22 bytes for a 1-indexed version:

ＦＮ⊞υ⊕↨Ｅι∧¬﹪⊕ι⊕κ⊕§υκ¹Ｉυ

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

ＦＮ

Loop \$ n \$ times.

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

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

Ｉυ

Output the results.

alephalpha · Accepted Answer · 2023-10-12 02:59:00Z

2

PARI/GP, 31 bytes

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

Attempt This Online!

edited Oct 12 at 2:59

answered Oct 12 at 1:14

alephalpha

46.5k7 gold badges61 silver badges172 bronze badges

Add a comment |

G B · Accepted Answer · 2023-10-13 11:37:57Z

2

Ruby, 79 38 bytes

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

Try it online!

edited Oct 13 at 11:37

answered Oct 11 at 20:19

G B

21.3k1 gold badge19 silver badges51 bronze badges

Add a comment |

138 Aspen · Accepted Answer · 2023-10-13 13:08:11Z

2

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}]

edited Oct 13 at 13:08

answered Oct 12 at 13:36

138 Aspen

4,7651 gold badge3 silver badges13 bronze badges

\$\begingroup\$ 1+Tr[1+#0/@Most@Divisors@#]&. \$\endgroup\$
– alephalpha
Oct 13 at 3:12

Add a comment |

corvus_192 · Accepted Answer · 2023-10-13 14:10:53Z

2

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!

answered Oct 13 at 14:10

corvus_192

4,89712 silver badges23 bronze badges

Add a comment |

AZTECCO · Accepted Answer · 2023-10-23 12:34:32Z

2

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

edited Oct 23 at 12:34

answered Oct 13 at 4:15

AZTECCO

10.6k1 gold badge13 silver badges58 bronze badges

1

\$\begingroup\$ 10 bytes in v1.4.5 \$\endgroup\$
– Shaggy
Oct 22 at 22:10

Add a comment |

Aiden Chow · Accepted Answer · 2023-10-24 02:44:45Z

2

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!

edited Oct 24 at 2:44

answered Oct 23 at 5:26

Aiden Chow

12.7k1 gold badge14 silver badges53 bronze badges

Add a comment |

boltcapt · Accepted Answer · 2023-10-30 20:12:19Z

0

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.

edited Oct 30 at 20:12

answered Oct 27 at 19:41

boltcapt

1113 bronze badges

Add a comment |

Stack Exchange Network

Divisor chain counts (1 3 3 7 ...)

Example

I/O

Tests

Scoring

18 Answers 18

Jelly, 10 9 7 bytes

Python 3, 45 bytes

R, 44 bytes

Nekomata + `-n`, 6 bytes

05AB1E, 10 bytes

Rust, 63 54 bytes

(#2)

Rust, 63 bytes

(#0)

Rust, 63 bytes

(#1)

Uiua, 18 bytes

JavaScript (ES6), 35 bytes

Commented

JavaScript (Node.js), 37 bytes

Retina 0.8.2, 34 bytes

Charcoal, 21 bytes

PARI/GP, 31 bytes

Ruby, 79 38 bytes

Mathematica, 43 28 bytes

Haskell, 38 bytes

Japt v1.4.5 `-x`, 15 10 bytes

Desmos, 119 118 bytes

APL (Dyalog Unicode), 51 45 44 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
math
sequence
division
or ask your own question.

Linked

Hot Network Questions

Divisor chain counts (1 3 3 7 ...)

Example

I/O

Tests

Scoring

18 Answers 18

Jelly, 10 9 7 bytes

Python 3, 45 bytes

R, 44 bytes

Nekomata + -n, 6 bytes

05AB1E, 10 bytes

Rust, 63 54 bytes

(#2)

Rust, 63 bytes

(#0)

Rust, 63 bytes

(#1)

Uiua, 18 bytes

JavaScript (ES6), 35 bytes

Commented

JavaScript (Node.js), 37 bytes

Retina 0.8.2, 34 bytes

Charcoal, 21 bytes

PARI/GP, 31 bytes

Ruby, 79 38 bytes

Mathematica, 43 28 bytes

Haskell, 38 bytes

Japt v1.4.5 -x, 15 10 bytes

Desmos, 119 118 bytes

APL (Dyalog Unicode), 51 45 44 bytes

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

Nekomata + `-n`, 6 bytes

Japt v1.4.5 `-x`, 15 10 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
math
sequence
division
or ask your own question.