5
\$\begingroup\$

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.

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

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!

\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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