// 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 the d isare 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; } // 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 the d is 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; } // 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.
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.
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;} 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 the d is 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; } 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;} 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.