15
\$\begingroup\$

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:

The centered polygonal number p(5,3).


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: p_5(4) - p_5(2)

p_5(7) - p_5(6)

p_7(3) - p_7(1)

p_7(5) - p_7(4)

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
\$\endgroup\$
  • \$\begingroup\$ 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.) \$\endgroup\$ – xnor Nov 18 at 22:38
  • \$\begingroup\$ @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\$. \$\endgroup\$ – Peter Kagey Nov 18 at 22:59
  • 4
    \$\begingroup\$ 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? \$\endgroup\$ – Paŭlo Ebermann Nov 19 at 23:45

12 Answers 12

13
\$\begingroup\$

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.

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

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.
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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.) \$\endgroup\$ – Peter Kagey Nov 18 at 23:33
  • \$\begingroup\$ @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. \$\endgroup\$ – Neil Nov 19 at 0:19
  • \$\begingroup\$ 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?? \$\endgroup\$ – vrintle Nov 19 at 5:19
  • 1
    \$\begingroup\$ You can save a few bytes with the divisors builtin Ñ: Ñʒ3*<›}ÑɘO. \$\endgroup\$ – ovs Nov 19 at 6:30
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Neil Nov 19 at 9:46
4
\$\begingroup\$

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

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

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

Wolfram Language (Mathematica), 39 bytes

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

Try it online!

special thanks to @att for saving 20 bytes

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 39 bytes \$\endgroup\$ – att Nov 20 at 2:14
2
\$\begingroup\$

Charcoal, 24 bytes

NθFθFθFθ⊞υ×⁺³ι×⊕⊗κ⊕λI№υθ

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

Nθ

Input n.

FθFθFθ

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.

I№υθ

Count how many times this equals n.

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

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.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ xnor's more compact function comes in at 65 bytes in Python. \$\endgroup\$ – ovs Nov 19 at 11:09
  • \$\begingroup\$ @ovs Oh wow - thanks! :D \$\endgroup\$ – Noodle9 Nov 19 at 11:18
1
\$\begingroup\$

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

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

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.

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

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.

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

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

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.