Potential nonzero entries in an irregular sequence

Question

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.

sequence 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 code-golf rules apply. The shortest code in bytes wins.

Answer 1

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!

Answer 2

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.

Answer 3

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.

Answer 4

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

Answer 5

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 [1] from that list of lists)
       Ż        - prepend a zero
        Ė       - enumerate -> [[1,0],[2,[2]],[3,[3]],[4,[4,1]],...,[9,[9,1,2]],...,[16,[16,1,2,3]],...]
         S€     - sum each -> [[1,[4],[6],[8,5]...[18,10,11],...[32,17,18,19],...]
           Ḃ    - mod 2 -> [[1,[0],[0],[0,1],...,[0,0,1],...,[0,1,0,1],...]
            F   - flatten
             T  - truthy indices (1-indexed)
              ḣ - head to index (i)