16
\$\begingroup\$

The Alternating Harmonic Series is a well known convergent series.

1/1 - 1/2 + 1/3 - 1/4 + 1/5 - 1/6 + ...

"Clearly", it is obvious that it converges to the natural log of 2. Or does it?

Since the series is not absolutely convergent, by simply rearranging the terms, I can make it approach anything I want. Suppose I want the series to converge to e. All I'd have to do is this:

1/1 + 1/3 + ... + 1/65 - 1/2 + 1/67 + ... + 1/175 - 1/4

If you didn't catch the pattern, there isn't an obvious one. Here's how it works:

  1. Consider the terms of the alternating harmonic series in terms of positive and negative terms.
  2. Add together just enough positive terms to exceed our target (e). (aka sum > target)
  3. Subtract the next negative term.
  4. Go back to 2.

Note that at step 2, if our sum == target, you should add another positive term.

From this we can define a sequence associated with each number as follows:

  • Follow the algorithm above
  • For each positive term, output 1.
  • For each negative term, output 0.

Let's call this sequence the "Harmonious Bit Pattern" of a number. For example, the HBP of e begins as:

1, 1, 1, 1, <32 times>, 0, 1, 1, <54 times>, 0, 1, 1, ...

Your challenge:

You will be given:

  • a rational input target in the range [-10, 10] (note: even reaching 10 via the harmonic series takes many millions of terms). This may be a decimal (aka 1.1) or you may take a rational directly (aka 12/100)
  • a positive int n input, specifying the number of terms of the Harmonious Bit Pattern to output.

You are expected to output the exact Harmonious Bit Pattern of the target to the specified number of terms. You may output space separated values, comma separated, no separation, etc; just as long as the pattern of 0s and 1s is clearly visible and is read left to right with consistent separation.

Test Cases

>>> 0, 1
1
>>> 0, 2
10
>>> 0, 7
1000010
>>> 1, 10
1101011011
>>> 1.01, 3
110
>>> 1.01, 24
110101101101101101101101
>>> 2.71, 32
11111111111111111111111111111111
>>> 2.71, 144
111111111111111111111111111111110111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111
>>> -9.8, 100
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Note that since -9.8 is so large, the first 1 that would be output is somewhere around the 149496620th term (that was computed via floats, so the value might not be exact).

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

Perl, 69 bytes

use bigrat;$s+=.5/($s>$ARGV[$_=0]?-++$n:++$p-++$_/2),print for 1..pop

Takes inputs as command line arguments.

Explanation: bigrat enables fractions everywhere for accurate calculations. $s is the current sum of terms, $ARGV[0] is the target value, pop (same as $ARGV[1]) represents the number of terms, $p and $n represent the positive and negative term counts. $_ is either 1 or 0 depending on whether a positive or negative term was added.

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

Haskell, 92 91 90 bytes

import Data.Ratio
f=(.h 0 1 2).take
h a p q z|a>z=0:h(a-1%q)p(q+2)z|1<2=1:h(a+1%p)(p+2)q z

Usage example: f 24 1.01 -> [1,1,0,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1].

h builds the infinite bit pattern by carrying four parameters around: a is the current sum. p is the denominator of the next positive term, q for negative terms. z is the target number. f starts everything up and truncates the result to length n.

Edit: @Zgarb found a byte to save. Thanks!

\$\endgroup\$
  • \$\begingroup\$ Defining h a p q instead of h p q a saves a byte. \$\endgroup\$ – Zgarb Oct 14 '15 at 19:37
  • \$\begingroup\$ Should be noted that 7 bytes are spent on just trimming the infinite result list to one of length n. It would actually be much nicer to just give the infinite list as the result. \$\endgroup\$ – ceased to turn counterclockwis Oct 14 '15 at 20:33
1
\$\begingroup\$

Python 3, 128 124 bytes

from fractions import*
F=Fraction
*c,s=2,1,0
t=F(input())
for i in'x'*int(input()):w=s<=t;s+=F(w*2-1,c[w]);c[w]+=2;print(+w)

This makes use of Python's Fraction class.

from fractions import* 
F=Fraction
*c,s=2,1,0                # c = [2, 1]. s = 0
                          # c is my positive/negative term counter, s is the sum
t=F(input())              # input a fraction
for i in'x'*int(input()): # Do this for for the chosen number of terms, as per the spec
  w=s<=t;                 # "w" or which one do we choose? Positive or negative?
  s+=F(w*2-1,c[w]);       # w*2-1 gives 1 if w else -1. Gives 1 if we need to add, else -1
  c[w]+=2;                # Increment the coefficient we chose
  print(+w)               # Output that. The +w coerces the bool to an int.
\$\endgroup\$
  • 1
    \$\begingroup\$ 'x'*int(input())? \$\endgroup\$ – FryAmTheEggman Oct 14 '15 at 15:56

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.