Sums of square roots

Question

Program the sequence \$R_k\$: all numbers that are sum of square roots of some(maybe one) natural numbers \$\left\{\sum_{i\in A}\sqrt i\middle|A\subset \mathbb{N}\right\}\$, in ascending order without duplication. Outputting zero is optional.

You should do one of:

• Take an index k and output \$R_k\$, either 0 or 1 indexing
• Take a positive integer k and output the first \$k\$ elements of \$R\$
• Output the whole sequence

Shortest code in each language wins. Beware of floating error, which returns \$\sqrt 2+\sqrt 8=\sqrt {18}\$ twice using my raw code, which is disallowed.

---

First few elements:

(0,)1,1.4142135623730951,1.7320508075688772,2,2.23606797749979,2.414213562373095,2.449489742783178,2.6457513110645907,2.732050807568877,2.8284271247461903,3,3.1462643699419726,3.1622776601683795,3.23606797749979,3.3166247903554,3.414213562373095,3.449489742783178,3.4641016151377544,3.605551275463989,3.6457513110645907,3.6502815398728847,3.732050807568877,3.7416573867739413,3.8284271247461903,3.863703305156273,3.872983346207417,3.968118785068667,4,4.059964873437686,4.123105625617661,4.146264369941973,4.16227766016838,4.1815405503520555,4.23606797749979,4.242640687119286,4.3166247903554,4.358898943540674,4.377802118633468,4.414213562373095,4.449489742783178,4.464101615137754,4.47213595499958,4.5604779323150675,4.576491222541475,4.58257569495584,4.60555127546399,4.645751311064591,4.650281539872885,4.685557720282968,4.69041575982343,4.730838352728495,4.732050807568877,4.741657386773941,4.795831523312719,4.82842712474619,4.863703305156273,4.872983346207417,4.878315177510849,4.8818192885643805,4.894328467737257,4.898979485566356,4.9681187850686666,5,5.0197648378370845,5.048675597924277,5.059964873437686,5.06449510224598,5.095241053847769,5.0990195135927845,5.123105625617661,5.146264369941973,5.155870949147037,5.16227766016838,5.1815405503520555,5.196152422706632,5.23606797749979,5.242640687119286,5.277916867529369,5.287196908580512,5.291502622129181,5.3166247903554,5.337602083032866,5.358898943540674,5.377802118633468,5.382332347441762,5.385164807134504,5.39834563766817,5.414213562373095,5.449489742783178,5.464101615137754,5.47213595499958,5.4737081943428185,5.4741784358107815,5.477225575051661,5.5373191879907555,5.55269276785519,5.5604779323150675,5.5677643628300215,5.576491222541474

Answer 1

M, 9 8 bytes

ŒP½ḅ1QṢḣ

Try it online!

Outputs the exact values (in the form sqrt(n), and by composing these with products and sums). Very similar to hyper-neutrino's answer, but doesn't fail due to floating point errors.

Outputs the first \$k\$ elements of \$R_k\$.

This times out on TIO for \$k \ge 10\$.

-1 byte (indirectly) thanks to DLosc's SageMath answer, so be sure to give that an upvote

How it works

ŒP½ḅ1QṢḣ - Main link. Takes k on the left
ŒP       - Powerset of [1, 2, ..., k]
  ½      - Square root of each; [[], [1], [sqrt(2)], ..., [1, sqrt(2), ..., sqrt(k)]]
   ḅ1    - Convert each from base 1, summing them
     QṢ  - Remove duplicates and sort
       ḣ - Take the first k elements

Answer 2

SageMath, 62 bytes

lambda k:sorted({*map(sum,powerset(map(sqrt,range(k+1))))})[k]

SageMath is a computer algebra system built on top of Python--the right choice if you want Python syntax without Python floating-point errors. Outputs exact values, written like sqrt(2) + 1, 0-indexed starting with 0. Try it here!

Explanation

Uses the "powerset of the first several square roots" approach:

lambda k:                       Anonymous function that takes an index k
                         [k]    and returns the kth element
         sorted(        )       of the following list sorted ascending:

                    range(k+1)  List of integers from 0 through k inclusive
               map(sqrt,     )  Square root of each
       powerset(             )  All possible subsets of the list of square roots
  map(sum,                   )  Sum of each subset
 {*                          }  Splat that list into a set, removing duplicates

(Passing a set to sorted automatically casts it to a list in Python--TIL.)

Answer 3

Wolfram Language (Mathematica), 44 42 bytes

1-indexed, output includes 0. First duplicates are removed, then numbers are converted to a numerical value to make the sorting shorter.

Sort[N[{}⋃Tr/@√Subsets@Range@#]][[#]]&

Try it online!

Answer 4

R, 261 169 157 bytes

Edit: substantial code golfing at the expense of now running painfully slowly for any input higher than 6 (although the underlying algorithm should still be valid if given sufficient time & resources)

function(x)sort(rowSums(unique(t(apply(expand.grid(rep(list(unlist(sapply(-1:x+1,n))),x+1)),1,sort)))^.5))[x]
n=function(x,y=2)`if`(y<x,if(x%%y^2)n(x,y+1),x)

Try it online!

Base R is subject to floating-point inaccuracies, so this rather long code attempts to avoid these by first constructing a list of lists of integers from which to sum the square-roots, in such a way that 'clashes' are avoided.

How?
We first note that 'clashes' - when a number can be expressed as the sum of square-roots of integers in two different ways - happen for composite numbers with repeated prime factors.
For instance: sqrt(4) = sqrt(2x2) = 2*sqrt(1) = sqrt(1)+sqrt(1)
Or: sqrt(18) = sqrt(2x3x3) = 3*sqrt(2) = sqrt(2)+2*sqrt(2) = sqrt(2)+sqrt(8)

So, we first remove integers with repeated prime factors:

no_repeated_factors=
n=function(x,y=2)`if`(y<x,if(x%%y^2)n(x,y+1),x)

We then generate a list of all lists of combinations of non-negative integers that sum any integer value up to x (so, all combinations of x elements of 0...x), excluding those with repeated prime factors (this step is pretty slow & greedy):

combinations_of_integers_without_repeated_factors_that_sum_to_up_to_x=
b=unique(t(apply(expand.grid(rep(list(unlist(sapply(-1:x+1,n))),x+1)),1,sort)))

The sums of square-roots from this list shouldn't give any 'clashes', so now we can just use all these lists of lists of integers that sum to 1...x, calculate the sums of square roots, sort, and output the x-th one:

sums_of_sqrts=
function(x)sort(rowSums(b(x)^.5))[x]

Omitting the final [x] allows us to inspect the list of sums of square-roots - click here - to check that the 'clashes' have been correctly removed, although at high indexes there will obviously be some missing values that will only get added when higher values of x are used.

There's probably a slicker way to do this... (particularly in languages with built-ins for finding prime factors or generating integer partitions).

Answer 5

Ruby, 70 bytes

->n{r=(0..n).map{|x|x**0.5};r.product(*[r]*n).map(&:sum).uniq.sort[n]}

Try it online!

0-based, returns n-th number, very slow for n>6.

Answer 6

GNU-APL, 56 bytes

k←15◊a←{⍉(⍵⍴2)⊤⍳2⋆⍵}k◊b←{+/a[⍵;⍳k]/(1↓⍳k+1)*0.5}¨⍳2⋆k◊k↑b[⍋b]

a←{⍉(⍵⍴2)⊤⍳2⋆⍵}k                  ⍝ Power Set Matrix - every row is a selector
b←{+/a[⍵;⍳k]/(1↓⍳k+1)*0.5} ¨ ⍳2⋆k ⍝ for every row find the sum of sqrt of selected elements
k↑b[⍋b]                           ⍝ sort and take k elements from b

Answer 7

Japt, 12 bytes

Returns the nth term, 0-indexed and including 0

gUô¬à mx â ñ

Try it

gUô¬à mx â ñ     :Implicit input of integer U
g                :Index into
 Uô              :  Range [0,U]
   ¬             :  Square roots
    à            :  Powerset
      m          :  Map
       x         :    Reduce by addition
         â       :  Deduplicate
           ñ     :  Sort

Answer 8

05AB1E, 5 bytes

∞ætOê

Outputs the entire sequence. Takes an infinite amount of time to generate the sequence, but works in theory.

∞ætOê  # full program
   O   # push list of sums of...
       # (implicit) each element in...
  t    # square root of...
       # (implicit) each element in...
       # (implicit) each element in...
 æ     # powerset of...
∞      # [1, 2, 3, ...]...
    ê  # sorted without duplicates
       # implicit output