14
\$\begingroup\$

A truncated square-pyramid of height \$h\$ has \$h\$ square layers where each layer has a side \$1\$ greater than the one above it, apart from the top layer which is a square of blocks with a given side length.

Here is a truncated square-pyramid of height \$7\$ and top side-length \$4\$ viewed from the side:

             side length   blocks
   ████          4          16
  ▐████▌         5          25
  ██████         6          36
 ▐██████▌        7          49
 ████████        8          64
▐████████▌       9          81
██████████      10         100
                   Total = 371

It requires \$\sum_{i=4}^{10}i^2=371\$ blocks to construct.


A truncated square-pyramid garden of size \$N\$ consists of truncated, square-pyramids of heights \$1\$ to \$N\$ where the \$n^{th}\$ tallest pyramid has a top side-length of \$x\$ where \$x\$ is the remainder after dividing \$N\$ by \$n\$ unless there is no remainder in which case \$x=n\$.

Here is a side-on view of a pyramid garden with \$N=6\$ pyramids, arranged from tallest to shortest:

N=6                ▐▌
                   ██     ██
                  ▐██▌   ▐██▌   ▐██▌
                  ████   ████   ████   ██
                 ▐████▌ ▐████▌ ▐████▌ ▐██▌ ▐▌
                 ██████ ██████ ██████ ████ ██  ██████
          height   6      5      4     3   2     1
               n   1      2      3     4   5     6
remainder of N/n   0      0      0     2   1     0
 top side-length   1      2      3     2   1     6  

This garden takes \$337\$ blocks to construct.

Task

Given a positive integer, \$N\$, calculate the number of blocks required to build a truncated square-pyramid garden of size \$N\$.

You are not required to handle size zero (just in case that causes an edge case for anyone).

Since this is a sequence, you may instead opt to output the block counts for all gardens up to size \$N\$ (with or without a leading zero, for size zero), or generate the block counts indefinitely without input (again a leading zero is acceptable). It's not currently in the OEIS, and neither is its two-dimensional version.

This is , so the shortest code in each language wins.

Test cases

The first \$100\$ terms of the sequence are (starting with \$N=1\$):

1, 9, 28, 80, 144, 337, 455, 920, 1251, 1941, 2581, 4268, 4494, 7065, 9049, 11440, 13299, 19005, 20655, 28544, 31140, 37673, 45305, 59360, 59126, 73289, 86256, 101124, 109647, 136805, 138364, 170780, 184520, 211485, 241157, 275528, 272869, 326729, 368320, 414692, 424823, 499261, 510708, 596140, 636361, 680537, 753508, 867036, 857345, 966889, 1027920, 1130172, 1197747, 1358369, 1393684, 1528840, 1571095, 1712605, 1860668, 2083248, 2023267, 2261821, 2445122, 2584136, 2685714, 2910217, 2980225, 3298056, 3459910, 3719313, 3824917, 4206640, 4128739, 4534965, 4846194, 5081240, 5308615, 5695545, 5827090, 6349936, 6395099, 6753185, 7173903, 7783720, 7688846, 8192521, 8679955, 9202980, 9429730, 10177969, 10090513, 10725680, 11134432, 11766133, 12407705, 13134004, 13024244, 13979357, 14523352, 15111244

Note: there is a surprisingly terse Jelly solution to find for this one, happy hunting!

Here's a hint that might help get you thinking about a different approach:

In Jelly lists are 1-indexed and indexing is modular, so finding the top side-length could be calculated by using \$N\$ to index into a list of [1,2,...,n].

2022-03-15: If you just want to see this solution I have now posted it below.

\$\endgroup\$
0

15 Answers 15

4
\$\begingroup\$

Python 3, 62 bytes

-2 bytes thanks to Neil!

lambda N:sum((N%~n-~h)**2for n in range(N)for h in range(n,N))

Try it online!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ sum((N%~n+h+1)**2for n in range(N)for h in range(n,N)) saves a byte. \$\endgroup\$
    – Neil
    Feb 21 at 16:58
  • 1
    \$\begingroup\$ @Neil Yes, thank you! And I can keep the +h+1 -> -~h for 62 \$\endgroup\$
    – ovs
    Feb 21 at 17:01
4
\$\begingroup\$

JavaScript (Node.js), 63 61 bytes

n=>eval("for(x=y=0;x++<n;)for(z=0;z++<=n-x;)y+=(~-n%x+z)**2")

Try it online!

Shortened by @ophact.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ (n-1)%x -> ~-n%x \$\endgroup\$
    – ophact
    Feb 21 at 17:06
4
\$\begingroup\$

R, 58 49 bytes

function(N){for(i in 1:N)F=F+(x=i:N+N%%-i)%*%x
F}

Try it online!

Relatively straightforward implementation of the spec.

R, 58 54 bytes

function(N)sum(unlist(Map(seq,N%%-(1:N)+1:N,l=N:1))^2)

Try it online!

Slightly more interesting but longer; relies on the same logic as above to generate the size of the top of each tower.

\$\endgroup\$
1
  • \$\begingroup\$ -1 byte for the second one. \$\endgroup\$
    – pajonk
    Feb 22 at 11:07
3
\$\begingroup\$

Jelly, 11 bytes

Rr_"N%RƊF²S

Try it online!

R              Range [1..n]
 r             Range each to n: [[1..n], [2..n], …, [n]]
    N%RƊ       [(-n)%1, …, (-n)%n]
  _"           Vectorize subtract
        F²S    Flatten, square, sum
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Perhaps unsurprisingly, this is not as short as my "surprisingly terse Jelly solution", however, it's certainly a nice answer. \$\endgroup\$ Feb 22 at 16:50
  • 1
    \$\begingroup\$ @JonathanAllan maybe you can at least give a hint? :) \$\endgroup\$
    – Lynn
    Feb 22 at 19:57
  • 1
    \$\begingroup\$ Hint added to the question - I know that you know what I've said in it, but it might help as an anchor of sorts. \$\endgroup\$ Feb 23 at 0:52
2
\$\begingroup\$

APL+WIN, 47 38 bytes

Prompts for N

+/∊((((n=0)×i)+n←i|N)+¯1+⌽⍳¨i←⍳N←⎕)*¨2

Try it online! Thanks to Dyalog Classic

\$\endgroup\$
2
\$\begingroup\$

05AB1E, 14 11 bytes

L(%ā.sR+˜nO

Try it online or verify the first 25 test cases.

Explanation:

    #  e.g. input=6
L   # Push a list in the range [1, (implicit) input]
    #  STACK: [1,2,3,4,5,6]
(   # Negate each value
    #  STACK: [-1,-2,-3,-4,-5,-6]
%   # Modulo the implicit input by these values
    #  STACK: [0,0,0,-2,-4,0]
ā   # Push a list in the range [1,length] (without popping)
    #  STACK: [0,0,0,-2,-4,0],
    #         [1,2,3,4,5,6]
.s  # Get its suffixes
    #  STACK: [0,-4,-2,0,0,0],
    #         [[6],[5,6],[4,5,6],[3,4,5,6],[2,3,4,5,6],[1,2,3,4,5,6]]
R   # Reverse the list of suffixes
    #  STACK: [0,-4,-2,0,0,0],
    #         [[1,2,3,4,5,6],[2,3,4,5,6],[3,4,5,6],[4,5,6],[5,6],[6]]
+   # Add the values in the two lists at the same positions together
    #  STACK: [[1,2,3,4,5,6],[2,3,4,5,6],[3,4,5,6],[2,3,4],[1,2],[6]]
˜   # Flatten to a single list
    #  STACK: [1,2,3,4,5,6,2,3,4,5,6,3,4,5,6,2,3,4,1,2,6]
n   # Square each integer
    #  STACK: [1,4,9,16,25,36,4,9,16,25,36,9,16,25,36,4,9,16,1,4,36]
O   # Sum them together
    #  STACK: 337
    # (after which the result is output implicitly)
\$\endgroup\$
1
  • 2
    \$\begingroup\$ I have 9 in the legacy version which could probably be golfed (My 05AB1E never was great :p) or might be possible in less using the current version. It uses a trick I feel is not all that likely to be found though ...let's see! \$\endgroup\$ Feb 21 at 17:05
2
\$\begingroup\$

JavaScript (Node.js), 61 bytes

N=>eval('for(k=n=0;n++<N;)for(c=e=N%n||n;c<=e+N-n;)k+=c*c++')

Try it online!

-2 by Polichinelle.

Iteratively calculates sum, which is shorter than direct calculation.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ @KevinCruijssen Thanks. I'm testing out a possible new solution that forgoes that stuff entirely, but if that doesn't work out, I'll apply your suggestion. \$\endgroup\$
    – ophact
    Feb 21 at 16:43
  • \$\begingroup\$ -2 bytes: for(c=e=N%n||n;c<=e+N-n;k+=c*c++);k -> for(c=e=N%n||n;c<=e+N-n;)k+=c*c++ \$\endgroup\$ Feb 21 at 17:04
2
\$\begingroup\$

Pari/GP, 37 bytes

N->sum(n=1,N,sum(i=n,N,(i-(-N)%n)^2))

Try it online!

\$\endgroup\$
2
\$\begingroup\$

C (gcc), 71 bytes

s;h;n;x;f(N){for(s=n=0;N/++n;)for(h=-~N-n,x=N%n?:n;h--;++x)s+=x*x;n=s;}

Try it online!

Inputs an integer \$N>0\$.
Returns the number of blocks needed to make a truncated square pyramid garden of size \$N\$.

\$\endgroup\$
2
\$\begingroup\$

JavaScript (ES6), 56 bytes

f=(N,n=N)=>n&&f(N,n-1)+(g=k=>n++<=N&&k*k+g(k+1))(N%n||n)

Try it online!


Faster, 66 bytes

A longer version that works in \$O(N)\$:

f=(N,n=N,k=N%n||n)=>n&&f(N,n-1)-(g=x=>x*(x+++x)*x/6)(k-1)+g(k+N-n)

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Jelly, 8 bytes

ịṡ¥Ɱ¹²FS

Try it online!

Uses the very clever tip supplied, but I'm not sure this quite inspires the description "surprisingly terse" yet... that ¹ just smells wrong!

More equivalent 8-byters:

  • ṡR⁸ịⱮ²FS
  • ịⱮṡR$²FS
  • ịⱮṡⱮ`²FS
  • RɓịⱮṡ²FS
   Ɱ¹       For each n in [1 .. N],
 ṡ          get a list of all substrings of [1 .. N] of length n,
ị ¥         and take the one at modular 1-index N.
     ²      Square each,
      F     flatten,
       S    and sum.
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Getting there, your sense of smell seems good too. \$\endgroup\$ Feb 23 at 22:45
1
\$\begingroup\$

Charcoal, 19 bytes

NθIΣEθΣX⁺⊕…ιθ﹪θ±⊕ι²

Try it online! Link is to verbose version of code. Explanation: Inspired by @KevinCruijssen's and @ovs's answers. Explanation:

Nθ                  Input `N` as a number
     θ              Input `N`
    E               Map over implicit range
          …         Range from
           ι        Current value
            θ       To input `N`
         ⊕          Vectorised Increment
        ⁺           Vectorised Plus
              θ     Input `N`
             ﹪      Modulo
                 ι  Current value
                ⊕   Incremented
               ±    Negated
       X          ² Vectorised Squared
      Σ             Take the sum
   Σ                Take the sum
  I                 Cast to string
                    Implicitly print
\$\endgroup\$
1
\$\begingroup\$

Ruby, 54 46 bytes

->n{(1..n).sum{|x|(x..n).sum{|y|(n%-x+y)**2}}}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Burlesque, 27 bytes

roJngsaj.%jiS~]q?+Z]FLqS[ms

Try it online!

Port of Kevin Cruijssen's answer

ro    # Range [1..N]
J     # Dup
ng    # Negate
sa    # Non-destructive length
j.%   # Modulo (implicit zip)
j     # Reorder stack
iS    # Generate tails
~]    # Drop final
q?+Z] # Zip and sum
FL    # Flatten
qS[   # Square
ms    # Map sum
\$\endgroup\$
1
\$\begingroup\$

Jelly, 5 bytes

Much of this post is in spoiler blocks, just in case anyone wants to try to find it for themselves since I mentioned it in the question.

ịⱮẆ²S

Try it online!

How?

Unrelated String got to the method in their answer, just not to the golfed code!

ịⱮẆ²S - Link: integer, N
  Ẇ   - all sublists of [1..N]
          e.g. N=6 -> [[1],[2],[3],[4],[5],[6]
                      ,[1,2],[2,3],[3,4],[4,5],[5,6]
                      ,[1,2,3],[2,3,4],[3,4,5],[4,5,6]
                      ,[1,2,3,4],[2,3,4,5],[3,4,5,6]
                      ,[1,2,3,4,5],[2,3,4,5,6]
                      ,[1,2,3,4,5,6]
                      ]
          i.e. for size in [1..N]:
                 for start in [1..N+1-len]
                   [start..start+size]
 Ɱ    - for each sublist:
ị     -   N index into sublist
          - indexing in Jelly is 1-indexed and modular so...
          e.g 6 ị [3,4,5,6] -> 4
          i.e N ị [start..start+size]
              -> (N mod size)+start-1 if (N mod size) != 0 else start+size
        e.g. 6 ịⱮ (6Ẇ) ->  [1,2,3,4,5,6,2,3,4,5,6,3,4,5,6,2,3,4,1,2,6]
              ...if these were grouped in lengths of [N..1] they
                 are our tower level side lengths:
                   [[1,2,3,4,5,6]  (height 6: [top..bottom])
                   ,[2,3,4,5,6]    (height 5: [top..bottom])
                   ,[3,4,5,6]      (height 4: [top..bottom])
                   ,[2,3,4]        (height 3: [top..bottom])
                   ,[1,2]          (height 2: [top..bottom])
                   ,[6]            (height 1: [top..bottom])
                   ]
   ²  - square (vectorises)
    S - sum

\$\endgroup\$
1
  • \$\begingroup\$ ...wow. I'm actually in awe. I thought that builtin might be involved somehow, but never thought about the structure of its output like that! \$\endgroup\$ Mar 20 at 3:54

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.