13
\$\begingroup\$

To get this sequence I just made up, which will subsequently be referred to as TSIJMU, consider the harmonic series:

\$ \frac{1}{2} + \frac{1}{3} + \frac{1}{4} ...\$

But what if you only add a term if it doesn't make the sum so far over 1, and otherwise subtract? Let's see an example here, starting at \$\frac{1}{2}\$:

Sum so far: 0, term: \$ \frac{1}{2} \$

\$ 0 + \frac{1}{2} = \frac{1}{2}\$, which is less than 1,so we add.

Sum so far: \$ \frac{1}{2} \$, term: \$ \frac{1}{3} \$

\$ \frac{1}{3} + \frac{1}{2} = \frac{5}{6}\$, which is less than 1,so we add.

Sum so far: \$ \frac{5}{6} \$, term: \$ \frac{1}{4} \$

\$ \frac{1}{4} + \frac{5}{6} = \frac{13}{12}\$, which is more than 1,so we subtract, yielding \$\frac{7}{12}\$.

If you do this forever, TSIJMU is the sequence of integers that are added when doing this. This goes 2,3,5,6,8, etc.

Rules

Your code must not fail due to floating point errors. As pointed out by Arnauld, this means your code may fail due to integer overflow errors. If this is the case, please provide a version which works for arbitrary input size.

As with all challenges, there are three ways you can output:

  • Take a number \$n\$ and return the nth item of TSIJMU
  • Take a number \$n\$ and return the first n items of TSIJMU
  • Print TSIJMU infinitely.

Scoring

This is , shortest wins!

Testcases

These are 0-indexed, but you can take 1-indexed.

0 => 2
3 => 6
9 => 17
25 => 48
58 => 113
90 => 177
156 => 308
352 => 700
479 => 953

As requested by Bubbler, the first 20 terms are:

2,3,5,6,8,10,12,13,15,17,19,21,23,25,27,29,31,33,34,36
\$\endgroup\$
7
  • 3
    \$\begingroup\$ "your code may fail due to integer overflow errors. If this is the case, please provide a version which works for arbitrary input size" - What do you mean by this? Does it mean, for instance, that if I answer in R (or any other general-purpose language which will error due to integer overflow eventually), I need to provide a second, independent, program that somehow avoids this effect? One obvious way to do this would be to import arbitrary-precision libraries, but then I will be changing the 'language' to R+gmp... \$\endgroup\$ Jun 29 at 7:17
  • 2
    \$\begingroup\$ "If you do this forever, TSIJMU is the sequence of integers that are added, stati. This goes 2,3,5,6,8, " Up until that point you described adding fractions. Where do the integers in that sequence come from? \$\endgroup\$
    – Anush
    Jun 29 at 7:27
  • 2
    \$\begingroup\$ Ok - I've added a non-overflowing version using arbitrary-precision GMP library, but it's a funny requirement, because (a) this avoids floating-point errors already, so I probably would have written the function differently from the outset if I wanted to use it, and (b) I can imagine there may be some other languages for which arbitrary-precision arithmetic or unlimited integers are not implemented, and if so it seems a shame to insist on this... \$\endgroup\$ Jun 29 at 9:25
  • 2
    \$\begingroup\$ @Anush I assume it should read "TSIJMU is the sequence of integers whose inverses are added". \$\endgroup\$
    – aschepler
    Jun 29 at 19:35
  • 3
    \$\begingroup\$ Might be a worthy submission to the OEIS, they don't seem to have it currently... \$\endgroup\$ Jun 29 at 20:51

16 Answers 16

9
\$\begingroup\$

Python 3.8, 54 bytes

-1 byte thanks to @ovs
-4 bytes thanks to @att

Outputs the sequence indefinitely.

a=b=n=2
while a:=a*n+[b,-b][a*n>b!=print(n)]:b*=n;n+=1

Try it online!

Although the code is heavily golfed, the idea is a straightforward implementation. a and b are the numerator and denominator of the current fraction. To add two fractions, we can use a simple formula: a/b + c/d => (ad + cb) / bd.

\$\endgroup\$
4
  • \$\begingroup\$ Heh, I figured Fraction took too much space and a smarter solution could beat a built-in one using the module. +1 \$\endgroup\$
    – hyper-neutrino
    Jun 29 at 6:05
  • 2
    \$\begingroup\$ As with hyper's solution, everything can be initialized as 1: TIO. After the second iteration a and b are lower by a factor of 2, but that doesn't change the value of the fraction \$\endgroup\$
    – ovs
    Jun 29 at 6:14
  • 1
    \$\begingroup\$ 55 bytes \$\endgroup\$
    – att
    Jun 29 at 6:48
  • 1
    \$\begingroup\$ @att Very clever; doing it in reverse (and checking if the result is negative). It took me a while to figure out what was going on! \$\endgroup\$ Jun 29 at 7:11
7
\$\begingroup\$

Husk, 13 bytes

W<Goḟε§e+≠1İ\

Try it online!

An infinite list.

woo, it works.

-2 bytes from ovs.

-4 bytes from Dominic Van Essen.

Explanation

Wo<0-Goḟε§e+`-1İ\
              1İ\ [1/2,1/3,1/4...
      Go      1   scan with 1 as intial value
         §e+`-    [a+b,a-b]
       ḟε         first element <=1
Wo                indices of pairs where
    -             difference is
  <0              < 0 (negative)
\$\endgroup\$
5
  • \$\begingroup\$ 17 bytes by using 1/1 and starting the scan at 1. This removes the need prepend a 0. \$\endgroup\$
    – ovs
    Jun 29 at 6:28
  • \$\begingroup\$ Very nice, didn't know you used husk as well! \$\endgroup\$
    – Razetime
    Jun 29 at 6:39
  • \$\begingroup\$ 14 bytes... \$\endgroup\$ Jun 29 at 16:47
  • \$\begingroup\$ Make that 13... \$\endgroup\$ Jun 29 at 16:59
  • 1
    \$\begingroup\$ I'd been thinking that absdiff didn't work on fractions all this time.. sigh \$\endgroup\$
    – Razetime
    Jun 30 at 2:27
5
\$\begingroup\$

R, 59 bytes

c=1
repeat `if`((F=F*(c=c+1)+T)>(T=T*c),F<-F-2*T/c,show(c))

Try it online!

Prints the sequence until it reaches the TIO output limit.

The numerator & denominator of the fraction so far are stored in F and T respectively. These won't error when they get too large, but R will assign them as Inf, beyond which point every integer will be (incorrectly) output, since Inf>Inf is evaluated as FALSE.

A non-overflowing version, using R+GMP to handle large integers, is 93 bytes (the R version installed on TIO seems to give an error, so here is a link to a working version on rdrr.io, with repeat exchanged for while(c<100) to force output).

\$\endgroup\$
4
\$\begingroup\$

Raku, 45 bytes

2.FatRat...{($!+=1/$_)>1??($!-=2/$_)!!.say}&1

Try it online!

Full program that outputs the sequence infinitely.

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

Wolfram Language (Mathematica), 35 34 bytes

#0[#+1/If[++i#>1,-Echo@i,i]]&[i=1]

Try it online!

Outputs the sequence indefinitely (up to $IterationLimit, 4096 by default).

Subtracts terms from 1 instead of adding from 0.


Without overriding $IterationLimit, 40 bytes:

i=0;Do[i+=1/If[i>1/j,-Echo@j,j],{j,∞}]

Try it online!

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

Stax, 19 bytes

«efy}á╤2╧8ßÇæ→╔y¬µ!

Run and debug it

Making a husk answer for this turned out to be very difficult. Here's a stack based one for the moment.

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

Python 3, 78 bytes

from fractions import*
v=i=Fraction(1)
while 1:i+=1;v-=(v>1/i!=print(i)or-1)/i

Try it online!

-8 bytes thanks to ovs
-1 byte thanks to Jo King (the number can't be exactly 1, also thanks to Bubbler for the pseudo-proof of this)
-2 bytes thanks to att

\$\endgroup\$
3
  • 1
    \$\begingroup\$ 85 bytes by initializing both v and i as 1 and a slightly shorter conditional expression. \$\endgroup\$
    – ovs
    Jun 29 at 5:46
  • 1
    \$\begingroup\$ 81 bytes \$\endgroup\$
    – ovs
    Jun 29 at 5:55
  • \$\begingroup\$ 78 bytes \$\endgroup\$
    – att
    Jun 29 at 6:41
2
\$\begingroup\$

Perl 5, 42 bytes

This prints TSIJMU infinitely:

$i=1;1while$s+=1/++$i*($s+1/$i<1?say$i:-1)

Try it online!

...or until Try It Online reaches its limit of 128 KiB of output. Exploits that say$i prints that sequence number and then returns 1.

This is seven bytes longer and takes n from stdin:

$i=1;$s+=1/++$i*($s+1/$i<1?$_--&&say$i:-1)while$_

Try it online!

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

JavaScript (with alert), 52 bytes

for(p=q=i=1n;;p*=i++)q*=i,p*i-p>q?alert(i,q+=p):q-=p

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ Nice! As specified above, you don't have to use BigInts as you're allowed to error because integer overflow. Please keep this version though. \$\endgroup\$
    – emanresu A
    Jun 29 at 6:31
1
\$\begingroup\$

Ly, 47 bytes

02s>n[<1f/+1G:![p:lu' o>,<]p[p1l/2*-0]pl`s>]>  

Try it online!

02s>n[<1f/+1G:![p:lu' o>,<]p[p1l/2*-0]pl`s>]>
02                                            # Init stack w/ "0" (sum) "2" (divisor)
  s>                                          # Stash the divisor, change to iterator stack
    n                                         # Read number of output items "N" from STDIN
     [                 >,<                >]  # Loop, iterates until "N" is 0
      <                                       # Switch to accumulator stack
       1f/+                                   # Calculate "(1/divisor)+accumulator" 
           1G:                                # Compare "accumulator>=1", duplicate answer
              ![p:        ]p                  # If-then, runs if "accumulator<1"
                  lu' o                       # Load the divisor, print as num, add " "
                       >,<                    # Switch to iterator stack, decr, switch back
                            [p      o]p       # If-then, runs if "accumulator>1"
                              1l/2*-          # Calc "2*(1/divisor)" and subtract
                                       l`s    # Increment divisor, stash it
                                            > # Switch to empty stack to suppress printing 
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 51 bytes

Nθ≔¹η≔⁰ζ≔¹εW‹Lυθ«≦⊕ε≧×εζ¿›ζ×η⊖ε≧⁻ηζ«≧⁺ηζ⊞υε»≧×εη»Iυ

Try it online! Link is to verbose version of code. Outputs the first n terms. Explanation:

Nθ

Input n.

≔¹η≔⁰ζ≔¹ε

Start with a running total of 0/1 and the last fraction as 1/1.

W‹Lυθ«

Repeat until enough terms have been collected.

≦⊕ε

Increment the denominator to get the next unit fraction.

≧×εζ

Multiply the running total by the denominator.

¿›ζ×η⊖ε≧⁻ηζ

If incrementing the running total would make it exceed the denominator then decrement it.

«≧⁺ηζ⊞υε»

Otherwise increment it and push the denominator to the list of results.

≧×εη

Divide the running total by the denominator.

»Iυ

Print the found terms.

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

05AB1E --no-lazy, 20 19 bytes

-1 byte thanks to Kevin Cruijssen!

λN*N<!©+DN!‹iN,ë®·-

Try it online!

There is no builtin fraction type, so everything is integers. (Ab)uses the recursive environment λ as an infinite loop that starts the iteration counter N at 1 and pushes a 1 to the stack initially.

λ                   # recursive environment
                    # generate infinite sequence of sums starting with a(0)=1
                    # pushes the last value to the stack, lets call this x
 N*                 # push N*x
    N<!©            # calculate (N-1)! and store a copy of the result in the register
        +D          # calculate N*x + (N-1)! and make a copy of the result
          N!‹       # is N*x + (N-1)! < N! ?
             iN,    # if so, N*x + (N-1)! / N! < 1 and print N
             ë®·-   # otherwise subtract (N-1)!*2 to get N*x - (N-1)!
\$\endgroup\$
3
  • \$\begingroup\$ -1 byte by removing the first D and changing \®- to ®·-. \$\endgroup\$ Aug 17 at 7:54
  • \$\begingroup\$ @KevinCruijssen thanks a lot. I feel like should be useful here, but the best I can do is the same length: tio.run/##AS8A0P9vc2FiaWX//… \$\endgroup\$
    – ovs
    Aug 17 at 8:06
  • \$\begingroup\$ Yeah, I was fiddling around with as well when I saw your iN,, but was only able to tie it with what you have, or alternatively without if-statement: D–≠·®*-. \$\endgroup\$ Aug 17 at 9:27
0
\$\begingroup\$

Haskell, 74 73 bytes

p=2#1$0
(n#y)x=(n?y)(x*n)$(n+1)#(y*n)
(n?y)a f|a+y>y*n=f$a-y|1>0=n:f(a+y)

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Japt v2.0a0, 29 bytes

Just ... hideous!

@¶Xõ!÷1 åÈ+Y§1©X+YªnXÃäÎèÉ}a2

Try it

\$\endgroup\$
0
\$\begingroup\$

Zephyr, 108 bytes

set s to 0
set i to 2
while 1=1
if(s+(/i))<1
set s to(/i)+s
print i
else
set s to s-(/i)
end if
inc i
repeat

Outputs infinitely. Try it online!

Implements the spec directly, using Zephyr's built-in rational numbers. Here it is ungolfed:

set sum to 0
set i to 2
while true
    if (sum + (/i)) < 1
        set sum to sum + (/i)
        print i
    else
        set sum to sum - (/i)
    end if
    inc i
repeat
\$\endgroup\$
0
\$\begingroup\$

Pip, 26 bytes

Wt*:oYt*o>y*Uo?t+y*Poy*o-t

Outputs infinitely. Try it here! Or, here's a 27-byte equivalent in Pip Classic: Try it online!

Explanation

Pip doesn't have rational numbers, so we'll use integer math instead. We store the numerator of the running sum in y (initially "", which evaluates to 0 in a numeric context); the denominator in t (initially 10, but any denominator greater than 0 will do, since the numerator is initially 0); and the index in o (initially 1). Each time through the loop, we want to:

  • Increment \$o\$
  • Test whether \$\frac y t + \frac 1 o \lt 1\$
    • If so, output \$o\$ and add \$\frac 1 o\$ to \$\frac y t\$
    • If not, subtract \$\frac 1 o\$ from \$\frac y t\$

For the test, observe that

$$ \frac i t + \frac 1 o \lt 1 \\ \frac{i \cdot o + t}{t \cdot o} \lt 1 \\ i \cdot o + t \lt t \cdot o \\ i \cdot o \lt t \cdot (o - 1) $$

We can combine this expression with the increment of \$o\$ by calculating \$t \cdot o\$ first, then incrementing \$o\$, then calculating \$i \cdot o\$.

For the update, we need

$$ y := y \cdot o \pm t \\ t := t \cdot o $$

Observing that t*:o is always truthy, does not depend on the value of y, and is a no-op if executed before the first time through the loop, we can use it as the while-loop header.

Wt*:oYt*o>y*Uo?t+y*Poy*o-t
                            t is 10, o is 1, y is "" (implicit)
 t*:o                       Multiply t by o and assign the result back to t
W                           and loop while the result is truthy (non-zero):
      t*o>                   Is t*o greater than
            Uo               o, incremented
          y*                 times y?
              ?              If so:
                   Po         Print o
               t+y*           and calculate t+y*o
                             Else:
                     y*o-t    Calculate y*o-t
     Y                       Set y to the calculated value
\$\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.