16
\$\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

This is now in the OEIS as A339010.

\$\endgroup\$
3
  • \$\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, 2020 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\$ Nov 18, 2020 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\$ Nov 19, 2020 at 23:45

14 Answers 14

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

\$\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.
\$\endgroup\$
5
  • \$\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\$ Nov 18, 2020 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, 2020 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, 2020 at 5:19
  • 1
    \$\begingroup\$ You can save a few bytes with the divisors builtin Ñ: Ñʒ3*<›}ÑɘO. \$\endgroup\$
    – ovs
    Nov 19, 2020 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, 2020 at 9:46
5
\$\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
\$\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
\$\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
\$\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

\$\endgroup\$
1
  • \$\begingroup\$ 39 bytes \$\endgroup\$
    – att
    Nov 20, 2020 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.

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

\$\endgroup\$
2
  • 1
    \$\begingroup\$ xnor's more compact function comes in at 65 bytes in Python. \$\endgroup\$
    – ovs
    Nov 19, 2020 at 11:09
  • \$\begingroup\$ @ovs Oh wow - thanks! :D \$\endgroup\$
    – Noodle9
    Nov 19, 2020 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.)

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

\$\endgroup\$
3
  • \$\begingroup\$ @ovs Used your observation on using xnor's more compact function in this answer too - thanks! :D \$\endgroup\$
    – Noodle9
    Nov 19, 2020 at 11:29
  • \$\begingroup\$ 62 bytes with a single for loop. \$\endgroup\$
    – Arnauld
    Nov 19, 2020 at 13:57
  • \$\begingroup\$ @Arnauld Very nice - thanks! :D \$\endgroup\$
    – Noodle9
    Nov 19, 2020 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.

\$\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
\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
7
  • \$\begingroup\$ 33 bytes (SBCS) using ⎕IO←0. \$\endgroup\$
    – Bubbler
    Nov 25, 2020 at 4:59
  • \$\begingroup\$ Any reason you only requested 50 rep for this? \$\endgroup\$
    – Adám
    Dec 6, 2020 at 14:04
  • \$\begingroup\$ @Adám It didn't qualify for any of the multipliers - it's not the shortest answer here, and I can't explain it very well. Actually, I should probably remove the request, since it was posted in 2020 \$\endgroup\$
    – user
    Dec 6, 2020 at 17:00
  • \$\begingroup\$ @user But your code is fully explained! \$\endgroup\$
    – Adám
    Dec 6, 2020 at 17:05
  • 1
    \$\begingroup\$ is enlist a.k.a. flatten. Check out APLcart. \$\endgroup\$
    – Adám
    Dec 6, 2020 at 17:12

Your Answer

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

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