7
\$\begingroup\$

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
\$\endgroup\$
9
  • 1
    \$\begingroup\$ Can we output the exact values, rather than the floats? \$\endgroup\$ Jun 4 at 17:21
  • \$\begingroup\$ @cairdcoinheringaahing Yes. \$\endgroup\$
    – l4m2
    Jun 4 at 17:21
  • \$\begingroup\$ For the floating point errors, is that allowed, or must our answer be correct in spite of floats? \$\endgroup\$ Jun 4 at 17:25
  • \$\begingroup\$ @cairdcoinheringaahing I'd disallow floating error issue on such small cases, some solutions taking forever isn't a reason as expection \$\endgroup\$
    – l4m2
    Jun 4 at 17:28
  • 3
    \$\begingroup\$ So the fp error is actually \$\sqrt{2} + \sqrt{8} \neq \sqrt{18}\$, perhaps you could word that a little clearer. \$\endgroup\$
    – Noodle9
    Jun 5 at 8:50
7
\$\begingroup\$

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
\$\endgroup\$
5
  • \$\begingroup\$ @NickKennedy Indeed I did, thanks! \$\endgroup\$ Jun 4 at 19:04
  • \$\begingroup\$ may be abit faster if we swap the order of ŒP and ½ \$\endgroup\$
    – Razetime
    Jun 5 at 13:05
  • \$\begingroup\$ @Razetime Unfortunately not, as ŒP automatically converts it to a range. Prepending a ½ might work to speed it up, but I'm not sure about the upper bound in that case and whether it works for all inputs \$\endgroup\$ Jun 5 at 13:40
  • \$\begingroup\$ If there are no precision errors then do you need to deduplicate and sort? \$\endgroup\$
    – Shaggy
    Jun 5 at 17:17
  • \$\begingroup\$ @Shaggy Yes, as the question says "in ascending order without duplication". If I didn't sort, it'd output \$\sqrt 6 \approx 2.4495\$ ahead of \$1 + \sqrt 2 \approx 2.4142\$, and if I didn't dedupliacte, it'd output (e.g.) \$\sqrt {18}\$ twice (as \$\sqrt 18\$ and as \$\sqrt 2 + \sqrt 8\$) \$\endgroup\$ Jun 5 at 17:23
4
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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

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

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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ What ensures protection from floating point errors? \$\endgroup\$
    – Jonah
    Jun 7 at 14:10
1
\$\begingroup\$

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!

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

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
\$\endgroup\$
8
  • \$\begingroup\$ Can you post a link (for instance on 'Try It Online') so that other people can try out your code? \$\endgroup\$ Jun 9 at 9:42
  • \$\begingroup\$ @DominicvanEssen: I can't seem to find any online service for GNU-APL. \$\endgroup\$
    – rajashekar
    Jun 9 at 9:57
  • \$\begingroup\$ Ah. Then it would be useful if you can explain how your code avoids outputting some elements twice due to floating-point errors (as exemplified in the challenge). \$\endgroup\$ Jun 9 at 11:19
  • \$\begingroup\$ There is a comparison tolerance variable ⎕CT that is used when comparing floating point values. The default seems small enough 1E-13 for this problem. \$\endgroup\$
    – rajashekar
    Jun 9 at 11:32
  • 1
    \$\begingroup\$ Yeah, that's what I was worrying about. Like sqrt(1e26) and sqrt(1+1e26), for instance... \$\endgroup\$ Jun 9 at 11:45
0
\$\begingroup\$

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

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
\$\endgroup\$
9
  • \$\begingroup\$ I'm not convinced that a program that never outputs anything can be considered a valid answer. It would be Ok if it outputs the sequence gradually (and so takes forever to finish), but the strategy of 'sorting' an infinite sequence (that obviously can't ever work) seems a bit dubious to me... \$\endgroup\$ Jun 9 at 9:41
  • \$\begingroup\$ @DominicvanEssen codegolf.meta.stackexchange.com/a/10582/94066 \$\endgroup\$
    – Makonede
    Jun 9 at 16:16
  • \$\begingroup\$ I don't think this justifies a program that doesn't ever output anything. Your link refers to the question "Should programs that are not proven to always terminate be valid?", and specifically considers the situation of programs that do terminate for almost all situations. Your program could be proven to never terminate, ever. \$\endgroup\$ Jun 9 at 16:35
  • \$\begingroup\$ @DominicvanEssen codegolf.meta.stackexchange.com/a/12949/94066. if you try it with something smaller, say TL instead of , it outputs a portion of the sequence. with something bigger like ₁L, it outputs a larger portion. therefore given infinite resources, it will eventually begin to output the list \$\endgroup\$
    – Makonede
    Jun 9 at 16:40
  • \$\begingroup\$ Well, I still don't agree that a program that provably never outputs anything is valid, even if a different version of the program can output something. I think that it would be better to modify the runnable version to output the k-th (or 1-to-kth) element(s), even if this costs a byte or two more. \$\endgroup\$ Jun 9 at 16:50

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.