# How many blocks make a "truncated square-pyramid garden"?

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.

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.

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

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

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

• (n-1)%x -> ~-n%x Feb 21 at 17:06

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

• -1 byte for the second one. Feb 22 at 11:07

# 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
• Perhaps unsurprisingly, this is not as short as my "surprisingly terse Jelly solution", however, it's certainly a nice answer. Feb 22 at 16:50
• @JonathanAllan maybe you can at least give a hint? :)
– Lynn
Feb 22 at 19:57
• 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. Feb 23 at 0:52

# 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

# 05AB1E, 14 11 bytes

L(%ā.sR+˜nO

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)
• 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! Feb 21 at 17:05

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

• @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. Feb 21 at 16:43
• -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++ Feb 21 at 17:04

# Pari/GP, 37 bytes

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

Try it online!

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

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

# 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.
• Getting there, your sense of smell seems good too. Feb 23 at 22:45

# Charcoal, 19 bytes

ＮθＩΣＥθΣＸ⁺⊕…ιθ﹪θ±⊕ι²

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

Ｎθ                  Input N as a number
θ              Input N
Ｅ               Map over implicit range
…         Range from
ι        Current value
θ       To input N
⊕          Vectorised Increment
⁺           Vectorised Plus
θ     Input N`
﹪      Modulo
ι  Current value
⊕   Incremented
±    Negated
Ｘ          ² Vectorised Squared
Σ             Take the sum
Σ                Take the sum
Ｉ                 Cast to string
Implicitly print

# Ruby, 54 46 bytes

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

Try it online!

# Burlesque, 27 bytes

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

Try it online!

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

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

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

• ...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! Mar 20 at 3:54