# Potential nonzero entries in an irregular sequence

## Background

A338268 is a sequence related to a challenge by Peter Kagey. It defines a two-parameter function $$\T(n,k)\$$, which counts the number of integer sequences $$\b_1, \cdots, b_t\$$ where $$\b_1 + \cdots + b_t = n\$$ and $$\\sqrt{b_1 + \sqrt{b_2 + \cdots + \sqrt{b_t}}} = k\$$. Since $$\k\$$ cannot be larger than $$\\sqrt{n}\$$, the relevant "grid" has an odd shape:

  n\k| 1  2 3 4
---+---------
1 | 1
2 | 0
3 | 0
4 | 0  2
5 | 0  0
6 | 0  2
7 | 0  0
8 | 0  2
9 | 0  0 2
10 | 0  4 0
11 | 0  0 2
12 | 0  6 0
13 | 0  0 2
14 | 0  8 0
15 | 0  0 4
16 | 0 12 0 2


More precisely, $$\n\$$-th row is limited to $$\1 \le k \le \lfloor \sqrt{n} \rfloor\$$.

Furthermore, this part of the grid has many known zero entries, as written in the OEIS page:

• $$\ T(n,1) = 0 \$$ for $$\n > 1\$$.
• $$\ T(n,k) = 0 \$$ if $$\n + k\$$ is odd, i.e. $$\n\$$ and $$\k\$$ have a different parity.

In this challenge, potential nonzero entries means the terms whose $$\(n,k)\$$ pair satisfies none of the above, i.e. $$\n+k\$$ is even, and either $$\n > 1\$$ or $$\(n,k) = (1,1)\$$.

Also, every sequence on the OEIS must be linearly laid out, so the numbers are "read by rows" as follows:

1, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 2, 0, 4, 0, 0, 0, 2, 0, 6, 0,
0, 0, 2, 0, 8, 0, 0, 0, 4, 0, 12, 0, 2, ...


In this sequence, the potential nonzero entries are at the following indices:

1-based: 1, 5, 9, 13, 16, 18, 22, 24, 28, 30, 34, 36, 38, ...
0-based: 0, 4, 8, 12, 15, 17, 21, 23, 27, 29, 33, 35, 37, ...


## Challenge

Output the 1-based or 0-based version of the sequence above.

I/O methods apply. You may use one of the following I/O methods:

• Take no input and output the sequence indefinitely,
• Take a (0- or 1-based) index $$\i\$$ and output the $$\i\$$-th term, or
• Take a non-negative integer $$\i\$$ and output the first $$\i\$$ terms.

Standard rules apply. The shortest code in bytes wins.

• Is $n, k \in \mathbb{Z}^+$?
– tsh
Jul 30, 2021 at 2:35
• @tsh n is a positive integer, and k is in the range mentioned in the post. Jul 30, 2021 at 2:38

# Python 3, 67 bytes

Prints the 0-based sequence forever.

d=n=k=0
while 1:k+=1;k**=k*k<=n;n+=k<2;k+n&1<(k>1%n)!=print(d);d+=1


Try it online!

Commented:

d=n=k=0
while 1:
k+=1                      # increment k
k**=k*k<=n                # k=k**1=k if k*k<=n, else k=k**0=1
n+=k<2                    # increment n if k is equal to 1
k+n&1<(k>1%n)!=print(d)   # print index d if k+n&1==0 (same parity) and k>1%n (k>0 for n==1 and k>1 for n>1)
d+=1                      # increment the index


Try it online!

# ARM T32 machine code, 34 bytes

b510 0001 d00c 2001 2204 3204 2302 3302
3001 001c 4364 1b14 d4f7 07a4 41a1 d1f6
bd10


Following the AAPCS, this takes a 0-based index in r0 and returns the 0-based entry at that index in r0.

Assembly:

.section .text
.syntax unified
.global sequence
.thumb_func
sequence:
push {r4, lr}     @ Save r4 and lr to the stack
movs r1, r0       @ Copy the index to r1
beq end           @ Special case: 0 -> 0; return immediately
movs r0, #1       @ Counter of grid entries processed, initialised to 1
movs r2, #4       @ r2 holds 4*n, for reasons to be seen later
nextrow:
adds r2, #4       @ Advance to the next row: r2 is increased by 4...
movs r3, #2       @ and r3, which holds 2*k, is set to 2.
nextcol:              @ With r3 being advanced immediately, this will skip k=1.
adds r3, #2       @ Increase r3 by 2 (increase k by 1)
adds r0, #1       @ Increment the counter
movs r4, r3       @ Duplicate the value of 2*k...
muls r4, r4, r4   @ square it, yielding 4*k^2...
subs r4, r2, r4   @ and subtract the square from 4*n.
bmi nextrow       @ If that's negative, the row is over;
@ the counter has already been incremented, counting for the k=1 entry in the next row.
lsls r4, r4, #30  @ The criterion is the parity of n+k, which is the same as that of n-k^2,
@ and hence bit #2 of 4*n-4*k^2. Shifting it 30 places left puts that bit in the carry flag,
@ and leaves r4 with a value of 0. (This is why the rescaling is needed: LSL 32 is invalid.)
sbcs r1, r4       @ Subtract from r1 the value of r4 (0) plus the inverted carry flag.
@ This counts down the number of potential nonzero entries needed.
bne nextcol       @ If it hasn't reached 0 yet, repeat.
end:
pop {r4, pc}      @ Restore the value of r4 from the stack and return.


# Jelly, 18 bytes

²‘½€RḂ¬ÐeḊŻ\$€FT1;ḣ


Try it online!

A monadic link taking an integer $$\n\$$ and returning the first $$\n\$$ terms of the sequence.

# 05AB1E, 19 bytes

Prints an infinite list of the 1-based sequence.

∞ε©tLε®+Éy®≠›‹]˜ƶ0K


Try it online!

∞ε            ]        # for n in [1, 2, ...]:
©                    #   store n in the register
tL                  #   range from 1 to sqrt(n)
ε        ]        #   for k in this range:
®+É              #     is n+k odd?
y®≠›          #     k > (n!=1)
‹         #     (n+k odd) < (k > (n!=1))
]        # close all loops
˜       # flatten the result into a single list
ƶ0K    # indices of 1's: multiply by index, remove 0's


A more literal port of my python answer is one byte longer:

[>Dn¾›i¼1}Ð¾+És¾≠›‹–


Try it online!

                       # d is the iteration index
# n is the counter variable
# k is on top of the stack
[                      # infinite loop, iteration index starts at 0
>                     # increment k
Dn¾›i  }             # if k**2 > n
¼1              # increment n and reset k to 1
Ð            # push two copies of k
¾+É         # is n+k odd?
s¾≠›     # is k > (n!=1)
‹    # (n+k odd?) < (k > (n!=1))
–   # if this is true, print the current iteration index


# Jelly, 15 bytes

Ḥ½ḶoƊ€ḊŻĖS€ḂFTḣ


A monadic Link accepting $$\i\$$ which yields a list of the first $$\i\$$ terms.

Try it online!

### How?

Ḥ½ḶoƊ€ḊŻĖS€ḂFTḣ - Link: positive integer, i
Ḥ               - double -> 2i
€          - for each (x in [1..2i]):
Ɗ           -   last three links as a monad, f(x):
½              -     square root (x) -> r
Ḷ             -     lowered range -> [0,1,2,3,4,...,floor(r)-1]
o            -     logical OR -> [x,1,2,3,4,...,floor(r)-1]
Ḋ         - dequeue (drops the leading  from that list of lists)
Ż        - prepend a zero
Ė       - enumerate -> [[1,0],[2,],[3,],[4,[4,1]],...,[9,[9,1,2]],...,[16,[16,1,2,3]],...]
S€     - sum each -> [[1,,,[8,5]...[18,10,11],...[32,17,18,19],...]
Ḃ    - mod 2 -> [[1,,,[0,1],...,[0,0,1],...,[0,1,0,1],...]
F   - flatten
T  - truthy indices (1-indexed)
ḣ - head to index (i)