Print this sequence I just made up

Question

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 sequence 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 code-golf, 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

Answer 1

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.

Answer 2

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)

Answer 3

Raku, 45 bytes

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

Try it online!

Full program that outputs the sequence infinitely.

Answer 4

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!

Answer 5

R, 59 58 bytes

Edit: -1 byte thanks to emanresu A

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

Answer 6

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.

Answer 7

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

Answer 8

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!

Answer 9

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

Answer 10

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!

Answer 11

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 

Answer 12

Charcoal, 51 bytes

Ｎθ≔¹η≔⁰ζ≔¹εＷ‹Ｌυθ«≦⊕ε≧×εζ¿›ζ×η⊖ε≧⁻ηζ«≧⁺ηζ⊞υε»≧×εη»Ｉυ

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

Ｎθ

Input n.

≔¹η≔⁰ζ≔¹ε

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

Ｗ‹Ｌυθ«

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.

»Ｉυ

Print the found terms.

Answer 13

Japt v2.0a0, 29 bytes

Just ... hideous!

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

Try it

Answer 14

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

Answer 15

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 y t + \frac 1 o \lt 1 \\ \frac{y \cdot o + t}{t \cdot o} \lt 1 \\ y \cdot o + t \lt t \cdot o \\ y \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 \$y \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

Answer 16

C (GCC), 75 bytes

n,d,i,j;s(a){for(n=i=1,d=j=2;a/i;n/d?n-=2*d/j:++i)n=n*++j+d,d*=j;return j;}

Try it online!

Overflows when the input is greater than 8.

How it works:

// n is the numerator, d the denominator, i the amount of numbers that have been added and j the denominator of the fraction that is supposed to be added.
n,d,i,j;
s(a)
{
    // The update statement of the for loop is moved to the end of the loop body for clearness (it's executed at the end of the loop anyways).
    // a / i is equivalent to a >= i, so we loop until i is greater than a
    for(n = i = 1, d = j = 2; a / i;)
        // Both n and d are multiplied by j, and the previous value of d is added to n.
        // The new fraction is (n*j + d) / (d*j).
        // (n*j)/(d*j) = n/d, so what's actually added to the fraction is d/(d*j), which can be rewritten as 1/j.
        n = n * ++j + d,
        d *= j,

        // n / d is non-zero iff n >= d, and n >= d iff n/d >= 1
        // If n/d >= 1, subtract what was previously added to n, twice.
        // Otherwise, increment i
        n / d ? n -= 2 * d / j : ++i;
    return j;
}

---

This 70-byte version also seems to work, although I'm not sure if it always does:

n,d,i,j;s(a){for(n=i=1,d=j=2;a/i;n/d?n-=2*d/j:++i)n=n*++j+d,d*=j;a=j;}

The 70-byte version stores j in a, which seems to have the same effect as returning j. If anyone knows, please tell me if that behavior is consistent and I'm allowed to use it.

Try It Online!

---

Here's a 127-byte version that overflows at a number of terms somewhere between 21 and 57:

long long n,d,i,j,k;s(a){for(n=i=1,d=j=2;a/i;n/d?n-=2*d/j:++i){n=n*++j+d,d*=j;for(k=1;k<99;)n%++k||d%k||(n/=k,d/=k);}return j;}

Try It Online!

It's pretty much the same as the first one, except the variables are long long integers rather than integers, and it includes for(k=1;k<99;)n%++k||d%k||(n/=k,d/=k);, which, for each number k from 1 to 98, divides n and d by k if they're both divisible by k.

Answer 17

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!