# Progressing Two's

Given an positive integer n (including 0 if you decide to support it), output all numbers in the generated sequence up to the index n. For the current test cases of the current challenge numbers are one-indexed. Feel free to submit 0-indexed answers though.

## Base sequence

We start from this sequence (NOT, but quite similar to, A160242):

1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 2, 2, ...


This sequence should be more understandable after formatting:

1,       2,       1,
1,    2, 2, 2,    1,
1, 2, 2, 2, 2, 2, 1,
and so on ...


However, our point is not to output this sequence. See the below procedure.

Here's an example of adding the sequence. Here, our sequence starts with 0:

We collect all intermediate results into the sequence.
The sequence
|     Output sequence: [0]
v
0 + 1 = 1 Output sequence: [0, 1]
1 + 2 = 3 Output sequence: [0, 1, 3]
3 + 1 = 4 Output sequence: [0, 1, 3, 4]
4 + 1 = 5 Output sequence: [0, 1, 3, 4, 5]
...

Our generated sequence is therefore

0, 1, 3, 4, ...



## Test cases

Here is a sample program outputting the sequence up to the input.

3 -> [0, 1, 3]
10 -> [0, 1, 3, 4, 5, 7, 9, 11, 12, 13]

• Are we allowed to start at 1; i.e. [1, 3, 4, 5, 7, 9, 11, 12, 13, 15] for 10? – hyper-neutrino Mar 13 '20 at 4:33
• Oh right I forgot about that whoops – hyper-neutrino Mar 13 '20 at 4:38
• @S.S.Anne This one insert two 1's. – Arnauld Mar 13 '20 at 11:52
• Is it just me or the title plus the whole structuring of the question is really misleading and confusing? – RGS Mar 13 '20 at 13:26
• The title mentions "adding square differences", so I automatically expect squares (either geometric or the squaring function $x \mapsto x^2$). And you mention "differences" but I can't find anything that vaguely makes me think of "square differences". Then the "1, 2 (xN), 1 repeated arbitrary times" is confusing and doesn't tell me how to generate the base sequence. Then you have the sentence where you explain how to go from the base seq. to the generated sequence. Which also is not clear at all... Then you also have this rule about my sequence not being allowed to start at 1..? – RGS Mar 13 '20 at 15:20

# 05AB1E, 9 7 bytes

ÝDtï-ü+


Port of @Bubbler's top APL answer, which uses the same formula as @xnor's Python answer:
$$f(n) = \sum_{k \in \{n,n+1\}}\left({k-\lfloor \sqrt k\rfloor}\right)$$

-2 bytes thanks to @Grimmy.

Try it online.

Explanation:

Ý        # Push a list in the range [0, (implicit) input-integer]
D       # Duplicate this list
t      # Take the square-root of each value
ï     # Cast it to an integer to floor it
-    # Subtract the values at the same positions from one another
ü   # For each overlapping pair:
# (after which the result is output implicitly)


Implementing the steps described in the challenge description would be 13 bytes instead:

2∞и1δš€û˜.¥I£


Try it online.

Or 2∞и1δš€û could alternatively be ÅÉÅ21δ.ø.

Try it online.

Explanation:

 ∞             # Push an infinite positive list: [1,2,3,...]
2 и            # Repeat 2 that many times as list: [[2],[2,2],[2,2,2],...]
δ          # For each inner list:
1 š         #  Prepend a leading 1: [[1,2],[1,2,2],[1,2,2,2],...]
€        # For each inner list:
û       #  Palindromize it: [[1,2,1],[1,2,2,2,1],[1,2,2,2,2,2,1],...]
˜      # Flatten the list of 1s and 2s: [1,2,1,1,2,2,2,1,1,2,2,2,2,2,1,...]
.¥    # Undelta it (cumulative sum with 0 automatically prepended):
#  [0,1,3,4,5,7,9,11,12,13,15,17,19,21,23,24,25,...]
I£  # Leave the first input amount of items from this infinite list
# (after which the result is output implicitly)

ÅÉ             # Push a list of odd numbers below or equal to the (implicit) input
#  i.e. 6 → [1,3,5]
Å2           # Repeat a list of 2s for each inner value: [[2],[2,2,2],[2,2,2,2,2]]
δ         # For each inner list:
1 .ø       #  Surround it with 1s: [[1,2,1],[1,2,2,2,1],[1,2,2,2,2,2,1]]
# (The rest is the same as above)


# Python 2, 52 bytes

n=p=0
exec"n+=1;r=n-n**.5//1;print p+r;p=r;"*input()


Try it online!

54 bytes

lambda N:[n-~n-n**.5//1-(n+1)**.5//1for n in range(N)]


Try it online!

It's a formula!

$$f(n) = 2n+1 - \lfloor \sqrt n\rfloor - \lfloor \sqrt {n+1} \rfloor$$

This can also be split up as

$$f(n) = \sum_{k \in \{n,n+1\}}\left({k-\lfloor \sqrt k\rfloor}\right)$$

Note that $$\k-\lfloor \sqrt k\rfloor\$$ is the number of non-squares from $$\1\$$ to $$\k\$$ inclusive.

# APL (Dyalog Extended), 14 12 bytes

0,2+/⍳-⌊∘√∘⍳


Try it online!

Uses xnor's formula of

$$f(n) = \sum_{k \in \{n,n+1\}}\left({k-\lfloor \sqrt k\rfloor}\right)$$

### How it works

0,2+/⍳-⌊∘√∘⍳
⍳-       ⍝ 1..n minus...
⌊∘√∘⍳  ⍝ floor(sqrt(1..n))
2+/         ⍝ Add two consecutive pairs
⍝ giving first n items of the sequence except leading 0
0,            ⍝ Prepend the leading 0


# APL (Dyalog Extended), 14 bytes

⊢↑2(∧+/,2××/)⍳


Try it online!

Based on the observation that the sequence is the union of all odd numbers and the numbers in the form of $$\2n(n+1), n \ge 0\$$. Uses ⎕IO←0.

### How it works

⊢↑2(∧+/,2××/)⍳  ⍝ Input: positive integer n
⍳  ⍝ Generate 0..n-1
2(      ×/)   ⍝ Pairwise product (0×1, 1×2, ..., (n-2)×(n-1))
2×      ⍝ Double it
+/,        ⍝ Concat with pairwise sum (0+1, 1+2, ..., (n-2)+(n-1))
∧           ⍝ Ascending sort the 2(n-1) numbers in total
⊢↑              ⍝ Take the first n numbers
⍝ For n=1, "overtake" from zero elements, giving single 0


(takeq 4)
q k=0:[1,3..k]++map(k+)(q$k+4)  Try it online! Uses a version of Bubbler's observation that the sequence alternates runs of consecutive odd numbers with an even number directly in between. # Haskell, 43 bytes (takescanl(+)0(q[2])) q r=1:r++1:q(2:2:r)  Try it online! Generates an infinite list of 1's and 2's, take the cumulative sums, and truncates to the input length. # Bash + GNU utilities, 33 29 bytes seq -f %0.fddv-r1-dv-+p$1|dc


Try it online!

This is another solution using @xnor's nice formula.

# JavaScript (ES7), 40 bytes

This is using the closed-form formula described below.

But because we're asked to output the $$\n\$$ first terms of the sequence, we need 19 bytes of wrapping code. :'-(

f=n=>n?[...f(n-1),(n-=n**.5)*2|n%1>0]:[]


Try it online!

### 21 bytes (n-th term, 1-indexed)

n=>(n-=n**.5)*2|n%1>0


Try it online!

Given $$\n\ge0\$$, we compute:

$$d(n)=2\cdot\lfloor n-\sqrt{n}\rfloor\\ f(n)=\cases{ d(n)&\text{if n is a square}\\ d(n)+1&\text{otherwise} }$$

The JS implementation uses a bitwise OR which implicitly floors $$\n-\sqrt{n}\$$ after it has been multiplied by $$\2\$$. But this leads to the same result.

# Perl 5-MList::Util=sum -n, 39 bytes

Shoutout to @xnor for the formula. This is essentially a port of his Python answer.

map{say$a+($n=$_-int$_**.5);$a=$n}1..$_  Try it online! # Jelly, 8 bytes R_Æ½$+ƝŻ


Try it online!

-5 bytes by porting xnor's formula (thanks Bubbler!)

-1 byte thanks to Nick Kennedy

# Explanation

Uses xnor's formula of:

$$f(n) = \sum_{k \in \{n,n+1\}}\left({k-\lfloor \sqrt k\rfloor}\right)$$

R_Æ½$+ƝŻ Main Link R range _$      subtract
Æ½                 square root floored (of each element)
Ż    prepend 0


Without xnor's formula, I have 10 bytes

# Jelly, 10 bytes

RÆ²Ẹ$Ɲ¬‘ÄŻ  Try it online! (range; for each pair of adjacent elements, check if either of them is square; logical NOT that and add one (gets the original 1,2 sequence), cumulative sum, prepend 0) • Maybe you could try different approaches like mine or xnor's. – Bubbler Mar 13 '20 at 7:44 • @Bubbler Thanks! – hyper-neutrino Mar 13 '20 at 12:27 • You can save a byte using Æ½ instead of ½Ḟ$. – Nick Kennedy Mar 13 '20 at 23:01
• @NickKennedy Oh whoops, I forgot that existed lol. Thanks! – hyper-neutrino Mar 13 '20 at 23:17
• @HyperNeutrino and a further byte by doing _Æ½)+ƝŻ – Nick Kennedy Mar 13 '20 at 23:20

# 05AB1E, 9 bytes

ENÅ²_©O=®


Try it online!

E           # loop for N from 1 to input:
NÅ²        #  is N a square?
_       #  logical not (0 if N is a square, 1 if not)
©      #  save in the register without popping
O     #  sum all numbers on the stack
=    #  print without popping
®   #  push the content of the register


# Python 3, 93 bytes

f=lambda n,x=0:(n-x)*[1]and[sum([j for i in range(1,n,2)for j in[1]+[2]*i+[1]][:x])]+f(n,x+1)


Try it online!

-21 bytes thanks to @Bubbler

• – Bubbler Mar 13 '20 at 5:01
• You can't exclude f= part because it's recursive. – Bubbler Mar 13 '20 at 5:06
• Ah. Well. Hmm. I'll edit it back in. – lyxal Mar 13 '20 at 5:10
• "And then +2 using the new f= trick" – user92069 Mar 13 '20 at 5:11
• Shhhhh. We don't talk about that here. :P – lyxal Mar 13 '20 at 5:12

# Python 2, 71 bytes

f=lambda n,k=0,w=3:n*[n]and[0]+[x-~(k>1)for x in f(n-1,~-k%w,w+2*0**k)]


Try it online!

# Charcoal, 17 bytes

ＩＥＥＮ…±⊕ι⊕ιＬ⁻↔ιＸι²


Try it online! Link is to verbose version of code. Based on @xnor's formula. Explanation:

   Ｎ                Input as a number m
Ｅ                 Map over implicit range 0..m-1
ι ι          Current index n
⊕ ⊕           Incremented (i.e. 1..m)
±              Negated
…               Exclusive range (i.e. -n .. n-1)
Ｅ                  Map over list of ranges
ι ι    Current range
Ｘ ²   Squares of values
↔       Absolute values
⁻        Remove the squares
Ｌ         Take the length
Ｉ                   Cast to string
Implicitly print


# C (gcc)-lm, 72 $$\\cdots\$$ 61 60 bytes

Saved a byte thanks to ceilingcat!!!

s;i;f(n){for(s=i=0;i<n;)printf("%d ",i-~i-s-(s=sqrt(++i)));}


Try it online!

Uses xnor's formula.

• Compiler flags are considered a different language now. Therefore, your solution is in the language "C (gcc) -lm". – S.S. Anne Mar 13 '20 at 15:54
• @S.S.Anne That's great! Makes sense as you can't use sqrt without -lm. Thanks! :-) – Noodle9 Mar 13 '20 at 15:59
• @ceilingcat Nice one - thanks! :-) – Noodle9 Mar 13 '20 at 16:46

# C (gcc), 81 bytes

r,c,i;f(n){for(r=c=0;~n;c++)for(i=++c;i--+2&&n--;r+=c+~i&&i+2)printf("%d ",r++);}


Some magic hackery used.

-4 bytes thanks to ceilingcat!

Try it online!

# Ruby, 52 50 bytes

->n,*w{n.times{|x|w+=[x,x*x,x*x];p w.sort[x+1]+x}}


Try it online!

### How:

The difference between n and f(n) shows an interesting pattern:

n   f   f-n
----------
0   0   0
1   1   0
2   3   1
3   4   1
4   5   1
5   7   2
6   9   3
7   11  4
8   12  4
9   13  4
10  15  5
11  17  6
12  19  7
13  21  8
14  23  9
15  24  9
16  25  9
17  27  10
18  29  11
19  31  12


In the rightmost sequence, every non-square number occurs only once, and every square number appears three times (except 0 which occurs only twice). I can build the required sequence as the sum of n and (f-n).

# Jelly, 7 bytes

Ż_Æ½$+Ɲ  A monadic Link accepting a positive integer, n, which yields a list of the first n entries. Try it online! ### How? Application of xnor's pair-wise addition formula $$\f(n) = \sum_{k \in \{n,n+1\}}\left({k-\lfloor \sqrt k\rfloor}\right)\$$ Ż_Æ½$+Ɲ - integer, n                       e.g. 10
Ż       - zero range                            [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Æ½    -   integer square-root (vectorises)    [0, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3]
_      -   subtract (vectorises)               [0, 0, 1, 2, 2, 3, 4, 5, 6, 6, 7]
Ɲ - for neighbours:
+  -   add                                  [0, 1, 3, 4, 5, 7, 9, 11,12,13]


# Husk, 10 bytes

ΘẊ+mṠ-o⌊√ḣ


Try it online!

# Japt, 8 bytes

Another port of xnor's formula.

ôÈ-¬fÃä+


Try it

ôÈ-¬fÃä+     :Implicit input of integer
ô            :Range [0,input]
È-          :Map & subtract
¬         :  Square root
f        :  Floored
Ã       :End map
ä+     :Consecutive pairs reduced by addition