Centerless Polygons

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

• Why does n=2 give 0? Isn't it the difference of triangular numbers 3 and 1? (Edit: Oops, I see the centered triangular numbers are a different sequence.) – xnor Nov 18 at 22:38
• @xnor—that's right. The centered triangular numbers are $A005448(n+1) = 3\frac{n(n+1)}{2} + 1$, and the centered $k$-gonal numbers are given by $k\frac{n(n+1)}{2} + 1$. – Peter Kagey Nov 18 at 22:59
• With uncentered I think of something else than this one (like the images in Wikipedia's Polygonal number article.) Maybe centerless is a better word? – Paŭlo Ebermann Nov 19 at 23:45

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.

05AB1E, 1716 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.

• If you did this the same way as me, "*" is the number of odd divisors of $n$, which is the number of ways to write $n$ as the difference of two triangular numbers. (See A001227.) – Peter Kagey Nov 18 at 23:33
• @PeterKagey Ah yes, of course; if I write i as the difference of two triangular numbers, this gives a solution for an n/i-gonal number. – Neil Nov 19 at 0:19
• I'm having some problems to relate your expl. to your output. Say, for n = 9, list is 1..3, and the odd divisors/factors are 1,3. So, sum is 4, but output is 3?? – vrintle Nov 19 at 5:19
• You can save a few bytes with the divisors builtin Ñ: Ñʒ3*<›}ÑÉ˜O. – ovs Nov 19 at 6:30
• @vrintle It's sum of the numbers of odd factors of the divisors of the original number. 1 has 1 odd factor. 2 is not a divisor. 3 has 2 odd factors. Total 3. – Neil Nov 19 at 9:46

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


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


JavaScript (ES6), 49 bytes

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


Wolfram Language (Mathematica), 39 bytes

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


Try it online!

special thanks to @att for saving 20 bytes

• 39 bytes – att Nov 20 at 2:14

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.

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!

• xnor's more compact function comes in at 65 bytes in Python. – ovs Nov 19 at 11:09
• @ovs Oh wow - thanks! :D – Noodle9 Nov 19 at 11:18

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

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!

• @ovs Used your observation on using xnor's more compact function in this answer too - thanks! :D – Noodle9 Nov 19 at 11:29
• 62 bytes with a single for loop. – Arnauld Nov 19 at 13:57
• @Arnauld Very nice - thanks! :D – Noodle9 Nov 19 at 15:55

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!

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


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