11
\$\begingroup\$

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 [0].
  • \$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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ 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\$. \$\endgroup\$ – tsh Jul 9 at 6:27
4
\$\begingroup\$

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

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

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.

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