12
\$\begingroup\$

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.

Adding the sequence

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]
Improve this question
\$\endgroup\$
7
  • \$\begingroup\$ Are we allowed to start at 1; i.e. [1, 3, 4, 5, 7, 9, 11, 12, 13, 15] for 10? \$\endgroup\$
    – hyperneutrino ♦
    Commented Mar 13, 2020 at 4:33
  • \$\begingroup\$ Oh right I forgot about that whoops \$\endgroup\$
    – hyperneutrino ♦
    Commented Mar 13, 2020 at 4:38
  • 2
    \$\begingroup\$ @S.S.Anne This one insert two 1's. \$\endgroup\$
    – Arnauld
    Commented Mar 13, 2020 at 11:52
  • 8
    \$\begingroup\$ Is it just me or the title plus the whole structuring of the question is really misleading and confusing? \$\endgroup\$
    – RGS
    Commented Mar 13, 2020 at 13:26
  • 8
    \$\begingroup\$ 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..? \$\endgroup\$
    – RGS
    Commented Mar 13, 2020 at 15:20

18 Answers 18

Reset to default
8
+50
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
6
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
5
\$\begingroup\$

Haskell, 42 bytes

(`take`q 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

(`take`scanl(+)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.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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:
      +  #  Add them together
         # (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)
Improve this answer
\$\endgroup\$
0
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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)
     +Ɲ     add adjacent pairs together
       Ż    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)

Improve this answer
\$\endgroup\$
4
  • 2
    \$\begingroup\$ Maybe you could try different approaches like mine or xnor's. \$\endgroup\$
    – Bubbler
    Commented Mar 13, 2020 at 7:44
  • \$\begingroup\$ You can save a byte using ƽ instead of ½Ḟ$. \$\endgroup\$
    – Nick Kennedy
    Commented Mar 13, 2020 at 23:01
  • 1
    \$\begingroup\$ @NickKennedy Oh whoops, I forgot that existed lol. Thanks! \$\endgroup\$
    – hyperneutrino ♦
    Commented Mar 13, 2020 at 23:17
  • \$\begingroup\$ @HyperNeutrino and a further byte by doing _ƽ)+ƝŻ \$\endgroup\$
    – Nick Kennedy
    Commented Mar 13, 2020 at 23:20
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
5
  • \$\begingroup\$ Quick and dirty recursive lambda, 93 bytes. \$\endgroup\$
    – Bubbler
    Commented Mar 13, 2020 at 5:01
  • \$\begingroup\$ You can't exclude f= part because it's recursive. \$\endgroup\$
    – Bubbler
    Commented Mar 13, 2020 at 5:06
  • \$\begingroup\$ Ah. Well. Hmm. I'll edit it back in. \$\endgroup\$
    – lyxal
    Commented Mar 13, 2020 at 5:10
  • \$\begingroup\$ "And then +2 using the new f= trick" \$\endgroup\$
    – user92069
    Commented Mar 13, 2020 at 5:11
  • \$\begingroup\$ Shhhhh. We don't talk about that here. :P \$\endgroup\$
    – lyxal
    Commented Mar 13, 2020 at 5:12
0
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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.

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

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!

Improve this answer
\$\endgroup\$
0
0
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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]
    $   - last two links as a monad:
  ƽ    -   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]
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Husk, 10 bytes

ΘẊ+mṠ-o⌊√ḣ

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.