# Number of distinct shadow transforms

## Background

Shadow transform of a 0-based integer sequence $$\a(n)\$$ is another 0-based integer sequence $$\s(n)\$$ defined with the following equation:

$$s(n) = \sum_{i=0}^{n-1}{(1 \text{ if } n \text{ divides } a(i), 0 \text{ otherwise})}$$

i.e. $$\s(n)\$$ is the number of terms in $$\a(0), \cdots, a(n-1)\$$ that are divisible by $$\n\$$.

$$\s(0)\$$ is always 0 because there are zero terms to consider, and $$\s(1)\$$ is always 1 because $$\a(0)\$$ is always divisible by 1. $$\s(2)\$$ may have a value of 0, 1, or 2, depending on how many terms out of $$\a(0)\$$ and $$\a(1)\$$ are even.

## Challenge

Given a non-negative integer $$\n\$$, compute the number of distinct shadow transforms of length $$\n\$$. This sequence is A226443.

The following is the list of first 11 terms for $$\n = 0, \cdots, 10\$$, as listed on the OEIS page.

1, 1, 1, 3, 12, 48, 288, 1356, 10848, 70896, 588480


Explanation: Let's call this sequence $$\f(n)\$$.

• $$\f(0)\$$ counts the number of empty sequences, which is 1 (since [] counts).
• $$\f(1)\$$ counts the possible number of [s(0)] which can only be .
• $$\f(2)\$$ counts [s(0),s(1)]s which can only be [0,1].
• Since s(2) can take any of 0, 1, or 2 independent of s(0) and s(1), $$\f(3)\$$ is 3.
• s(3) is also independent of s(0) through s(2) (because 3 is relatively prime to 2) and take a value between 0 and 3 inclusive, so $$\f(4) = 3 \cdot 4 = 12\$$.
• Finding $$\f(5)\$$ is slightly more complex because s(4) is tied with s(2). If s(4) == 4, all of a(0)..a(3) must be divisible by 4 (and therefore even), and s(2) can only be 2. If s(4) == 3, at least one of a(0) or a(1) must be even, and s(2) must be 1 or 2. Therefore, $$\f(5) = 12 + 12 + 12 + 8 + 4 = 48\$$.

Standard rules apply. I/O does NOT apply. The shortest code in bytes wins.

• It is easy to generate all arrays with $n$ elements each element in $0 \dots \text{LCM}\left(1,\dots,n\right)$ (to golf more bytes, I would choice $1\dots n^n$ instead), apply $s$ to it, and then count how many distinct results in all. But I don't know how to test it as it will not produce output in reasonable time even for $n = 5$.
– tsh
Jul 9, 2021 at 6:27

# Jelly, 13 bytes

Thanks to @ovs for the fix.

%Lċ0
*ṗ’ÇƤ€QL


Try it online!

The first line computes the shadow transform.

The second line looks at the shadow transform of all sequences of length n with elements in {1, 2, ..., n^n}.

• You're currently off by one, $f(3)$ should be $3$. µ -> ’ would fix this at the cost of a bit of effiency.
– ovs
Jul 9, 2021 at 13:01
• @ovs fixed, thanks. Jul 9, 2021 at 18:05
• You can group the helper link with Ʋ and save a byte - *ṗ’%Lċ0ƲƤ€QL Jul 9, 2021 at 18:12

# Python 2 (PyPy), 228 225 bytes

This is based on the first PARI implementation on OEIS and computes terms up to $$\n=6\$$ on TIO.

import math,itertools as I
L=math.log
R=range
n=input()
P=k=r=1
while k<n:k+=1;r*=k**int(P%k*L(n+.5)/L(k));P*=k*k
print len({tuple(sum(x%o<1for x in s[:o])for o in R(n))for s in I.product(*[[i+1for i in R(r)if-1<r%~i]]*~-n)})


Try it online!

Naive bruteforcing is obviously a lot shorter (100 bytes):

lambda n,R=range:len({tuple(sum(s/n**(n*x)%n**n%o<1for x in R(o))for o in R(n))for s in R(n**n**2)})


Try it online! Crashes for $$\n=4\$$ with a MemoryError, when R(n**n**2) tries to create a list of $$\2^{32}\$$ integers.