Centerless Polygons

Question

A centered polygonal number is a positive integer given by the number of vertices when a point is surrounded by (increasingly larger) polygons with the same number of sides, as shown below. For example, \$p_5(3) = 1 + 5 + 10 + 15 = 31\$ is a centered pentagonal number formed by taking a vertex and adding three layers of pentagons:

---

This question, however, concerns centerless polygonal numbers. In particular, we want to know how many ways we can write \$n\$ as the difference of two \$k\$-gonal numbers with \$k \geq 3\$—that is, a centered polygon with the center removed.

For example, \$35\$ can be written as the difference of two \$k\$-gonal numbers in five ways:

• \$p_5(4) - p_5(2) = 51 - 16\$,
• \$p_5(7) - p_5(6) = 141 - 106\$,
• \$p_7(3) - p_7(1) = 43 - 8\$,
• \$p_7(5) - p_7(4) = 106 - 71\$, and
• \$p_{35}(1) - p_{35}(0) = 36 - 1\$,

the first four of which are illustrated below:

The Challenge

This challenge will have you write a script that takes a positive integer n and outputs the number of ways to write \$n\$ as a centerless polygonal number.

Since this is a code-golf challenge, the shortest code wins.

The sequence begins:

0, 0, 1, 1, 1, 2, 1, 2, 3, 2, 1, 5, 1, 2, 5, 3, 1, 6, 1, 5, 5, 2, 1, 8, 3, 2, 6, 5, 1, 10, 1, 4, 5, 2, 5, 12, 1, 2, 5, 8, 1, 10, 1, 5, 12, 2, 1, 11, 3, 6, 5, 5, 1, 12, 5, 8, 5, 2, 1, 19, 1, 2, 12, 5, 5, 10, 1, 5, 5, 10, 1, 18, 1, 2, 12, 5, 5, 10, 1, 11, 10, 2

This is now in the OEIS as A339010.

Answer 1

Haskell, 42 bytes

f n=sum[0^mod n q|a<-[3..n],q<-[a,3*a..n]]

Try it online!

51 bytes

f n=sum[1|a<-[3..n],b<-[1,3..n],c<-[1..n],a*b*c==n]

Try it online!

The output is the number of ways to factor \$n=abc\$ into three positive factors, where \$a \geq 3\$, \$b\$ is odd, and \$c\$ is unconstrained.

Answer 2

05AB1E, 17 16 10 bytes

3÷ÝsÑÃÑÉOO

Try it online! Edit: Saved 5 bytes thanks to @ovs. Explanation:

3÷L         Get a list from `0` to `n//3`.
   sÑÃ      Keep only factors of `n`.
      ÑÉO   Number of odd divisors of each factor.
         O  Output the sum.

Answer 3

J, 29 bytes

[:+/@,[=[+/\\.@(*1+i.)~"+3+i.

Try it online!

[:+/@,[=[+/\\.@(*1+i.)~"+3+i.
                           i. 0…N-1
                         3+   3…N+2
                       "+     for each y in 3…N+2:
        [      (*1+i.)~       y * 0…N, thus f.e. 5 10 15 20 … for p_5
           \\.@               take every possible sublist
         +/                   and sum it
      [=                      which sums are equal to N?
[:+/@,                        count the true bits

Answer 4

Jelly, 10 bytes

:3ḍƇ⁸ÆDFḂS

A monadic Link accepting \$n\$ which yields the count.

Try it online! Or see the test-suite.

How?

:3ḍƇ⁸ÆDFḂS - Link: n
 3         - three
:          - (n) integer divide (3) -> x
   Ƈ       - filter keep those v in [1..x] for which:
  ḍ        -   (v) divides:
    ⁸      -     chain's left argument, n
     ÆD    - divisors (of each)
       F   - flatten
        Ḃ  - least significant bit (of each)
         S - sum

Answer 5

JavaScript (ES6), 49 bytes

Uses the method described by @xnor.

f=(n,d=k=1)=>k<=n&&!(n/~++k%d)+f(n,d>n||k--&&d+2)

Try it online!

Commented

f = (            // f is a recursive function taking:
  n,             //   n = input
  d = k = 1      //   d = odd divisor, k = other divisor
) =>             //
  k <= n &&      // stop if k is greater than n
  !(             // otherwise:
    n / ~++k     //   - increment k
    % d          //   - increment the final result if d is a divisor of n / (k + 1)
  ) +            //
  f(             // add the result of a recursive call:
    n,           //   - pass n unchanged
    d > n ||     //   - if d is greater than n, leave k unchanged and reset d to 1
    k-- && d + 2 //     otherwise, decrement k and add 2 to d
  )              // end of recursive call

Answer 6

Wolfram Language (Mathematica), 39 bytes

Sum[Boole[(2i j-i)∣#],{i,3,#},{j,#}]&

Try it online!

special thanks to @att for saving 20 bytes

Answer 7

Charcoal, 24 bytes

ＮθＦθＦθＦθ⊞υ×⁺³ι×⊕⊗κ⊕λＩ№υθ

Try it online! Link is to verbose version of code. Port of @xnor's answer. Explanation:

Ｎθ

Input n.

ＦθＦθＦθ

Create loops i, k and l ranging from 0 to n.

⊞υ×⁺³ι×⊕⊗κ⊕λ

Calculate a*b*c where a=i+3, b=2k+1 and c=l+1.

Ｉ№υθ

Count how many times this equals n.

Answer 8

Python 3, 84 65 bytes

Saved a whopping 19 bytes thanks to ovs!!!

lambda n,R=range:sum(n%q<1for a in R(3,n+1)for q in R(a,n+1,2*a))

Try it online!

Uses xnor's method from his Haskell answer.

Answer 9

Retina 0.8.2, 49 bytes

.+
$*
M!&`(.+)$(?<=^\1{3,})
m&`(.(..)*)$(?<=^\1+)

Try it online! Link includes test suite that checks all numbers from 1 to the input. Explanation:

.+
$*

Convert to unary.

M!&`(.+)$(?<=^\1{3,})

List (!) all (&) factors not greater than n/3.

m&`(.(..)*)$(?<=^\1+)

Count the number of odd factors of all the factors. (The M is implicit as this is the last stage.)

Answer 10

C (gcc), ^{79 63} 62 bytes

Saved a whopping 16 bytes thanks to ovs!!!
Saved a byte thanks to the man himself Arnauld!!!

a;q;s;f(n){for(s=0,q=a=3;n/q||n/(q=++a);)s+=n%(q-=2*a)<1;n=s;}

Try it online!

Uses xnor's method from his Haskell answer.

Answer 11

Ruby, 76 bytes

->n{(1..n/3).select{|k|n%k==0}.sum{|o|(1..o).select{|i|o%i==0}.sum{|j|j%2}}}

Try it online!

Based on Neil's answers.

Answer 12

Java 8, 73 bytes

n->{int r=0,a=2,t;for(;a++<n;)for(t=a;t<=n;t+=2*a)if(n%t<1)r++;return r;}

Port of @Noodle9's Python 3 answer, which uses the same method as @xnor's Haskell answer.

Try it online.

Explanation:

n->{               // Method with integer as both parameter and return-type
  int r=0,         //  Result-sum, starting at 0
      a=2,         //  Temp-integer `a`, starting at 2
      t;           //  Temp-integer `t`, uninitialized
  for(;a++<n;)     //  Loop `a` in the range [1, n]:
    for(t=a;t<=n;  //   Inner loop `t` in the range [a, n],
        t+=2*a)    //   in increments of 2a
      if(n%t<1)    //    If the input is evenly divisible by `t`:
        r++;       //     Increase the result-sum by 1
  return r;}       //  And after the loops, return the result-sum

Answer 13

MathGolf, 12 bytes

3/╒÷mÉî*──¥Σ

Try it online.

Explanation:

3/           # Integer-divide the (implicit) input-integer by 3
  ╒          # Pop and push a list in the range [0, input//3]
   ÷         # Check for each that they evenly divide the (implicit) input
             # (1 if truthy; 0 if falsey)
    m        # Then map each boolean to,
     É       # using the following three characters as inner code-block:
      î*     #  Multiply the boolean by the 1-based map-index
        ─    #  Pop and push a list of its divisors
         ─   # Flatten this list of list of integers
          ¥  # Modulo-2 on each
           Σ # And sum those together
             # (after which the entire stack joined together is output implicitly)

Answer 14

APL (Dyalog Unicode), 40 33 bytes (SBCS)

Saved 7 bytes thanks to @Bubbler!

Port of Neil's 05AB1E answer.

{+/∊(⊢(|⍨<2|⊢)1+⍳)¨⍵(⊢∩∨)⍳1+⌊⍵÷3}

Try it online!

{+/∊(⊢(|⍨<2|⊢)1+⍳)¨⍵(⊢∩∨)⍳1+⌊⍵÷3}
                          ⍳1+⌊⍵÷3 ⍝ Range to n//3 + 1
                    ⍵(⊢∩∨)       ⍝ Keep divisors of n
                   ¨              ⍝ For each divisor
   ∊(⊢(|⍨<2|⊢)1+⍳)               ⍝ A train to find odd divisors of the divisor, not sure how it works exactly
               1+⍳)               ⍝ Make a range from 2 to the divisor+1
    (⊢                           ⍝ On this side, just give back the divisor
      (|⍨<2|⊢)                   ⍝ Checks that the element of the range divides the divisor and that it's odd
      (|⍨                        ⍝ The possible divisor mod its divisor
         <                       ⍝ Is less than
          2|⊢)                   ⍝ 2 mod the divisor's possible divisor
   ∊                             ⍝ Turn into vector so a single sum is needed
 +/                               ⍝ Sum that