# Find the overall period from a list of frequencies

Inspired by http://xkcd.com/1331/

In this xkcd comic, there are several gifs that all blink with different frequency. I want to know what the period would be if was all a single GIF. Given a list of numbers representing the individual frequencies, output the period of the overall GIF.

Formal Definition

Input:

N
f1
f2
.
.
.
fN


Output:

P


Where N is the number of frequencies, fi is the ith frequency, and P is the resulting period of the total GIF.

You may choose to use any delimiting character you want(instead of \n), and you may exclude the N if you wish, and it will be inferred by the number of delimeters.

Some specifics

Frequencies are the closest double-precision floating point representation of the numbers provided as input.

The outputted period is a 64-bit unsigned integer, rounded(up on 0.5) to the nearest whole. Any input that would produce a period bigger than 2^64-1 is considered undefined behaviour.

Likewise any input <= 0 is considered undefined behaviour.

Win Condition

Code golf so shortest code wins!

• Possible spoiler... wouldn't this just be the product of the given frequencies? Commented Feb 19, 2014 at 23:50
• @crazedgremlin No it isn't, but you are pretty close. Commented Feb 20, 2014 at 0:30
• @crazedgremlin - If A is 2s and B is 4s, then the resulting period would be 4s, not 8s. Commented Feb 20, 2014 at 0:36
• Ah, I see, thanks. @Cruncher, what exactly do you mean by "frequency"? Repetitions per second or the amount of time a repetition takes? I assume the former, as that is usually what frequency means. Commented Feb 20, 2014 at 0:41
• There are at least 2 methods for this: Take the overall frequency as the GCD of the input frequencies and invert it. Or take the input frequencies, invert them all to get the periods and take the LCM as the overall period. I took the GCD. @DavidCarraher took the LCM. You just need to cope with the non-integers. Commented Feb 20, 2014 at 2:20

# APL, 4

∧/∘÷


∧ is both logical AND and numerical LCM (with domain over integers, floats, complex, rationals, whatever number stack is supported by the APL implementation) so ∧/ is reduction by LCM, or computing the LCM of an array.

Monadic ÷ is numeric inverse. So the composition ∧/∘÷ is the LCM of the inverses of the numbers supplied.

The other formula, inverse of the GCD, would be ÷∘(∨/), where the parentheses are needed to fix the precedence between ∘ and /.

You can try it online on http://tryapl.com/

Examples

      ∧/∘÷ .12 .02 3.9 .15 .99
100
∧/∘÷ (16÷5)(2÷3)(2.35)(1÷7)
420

• Holy bananas! Commented Feb 20, 2014 at 21:17
• @Cruncher that would be † )) ! in APL. Commented Feb 20, 2014 at 22:44
• Bravo. I think that we have a winner. Commented Feb 21, 2014 at 2:15
• Simply amazing. Hats off to you. Commented Feb 21, 2014 at 4:22

# Mathematica 43 28

## Second try

My first attempt was not correct, although it did have some of the necessary ingredients (LCM,Rationalize). The complete solution requires taking into account both the numerator and denominator of each frequency (expressed as a common fraction).

l is the list of frequencies.

Rationalizing 2.35 converts it to the common fraction 235/100.

f@l_:=LCM@@(1/Rationalize@l)


Assume that all GIFs fire at t=0.

The following approach does not require that the frequencies be expressed as "real numbers", ie. as decimal fractions. They may be other sort of fractions. The example below is a case where the fractions are in fifths, thirds, hundredths and sevenths.

If two or more frequencies are incommensurate (in which case at least one must be an irrational number) then there is no solution. In other words, there will be no point in time, t>0, at which all components fire at the same time.

Example1

f[{50, 10}]


1/10

Example 2

f[{16/5, 2/3, 2.35, 1/7}]


420

If we multiply the least overall period by each of the frequencies, we find a whole number of cycles in each case:

420*{16/5, 2/3, 2.35, 1/7}


{1344, 280, 987., 60}

(1344 hops of 16/5 units) lands at 420. (280 hops of 2/3 units) lands at 420. (987 hops of 2.35 units) lands at 420. (60 hops of 7 units) lands at 420.

• The right tool for the right job. Commented Feb 20, 2014 at 1:33
• I am not sure I understand. If the inputs are frequencies, the f[{50,10}] would mean the common cycle of signal that fires 50 times per second and a cycle that files 10 times per second? The correct answer would be 1/10 of a second, but f[{50, 10}] returns 1. Actually, lots of random things return an answer of 1. f[{345345, h}] returns 1. Commented Feb 20, 2014 at 2:27
• My original approach was incomplete (and therefore incorrect). I've amended it in such a way as to address your observation. The current solution also makes sense geometrically (using line segments against the real line). Commented Feb 20, 2014 at 3:23
• I was coming to post just such a solution, but you beat me to it. Very nice. Commented Feb 20, 2014 at 3:42
• @Jonathan. Yes, your approach was almost identical to mine. But I don't see the need for Round. Won't Rationalize and LCM guarantee that the results be integers? Commented Feb 20, 2014 at 3:56

## Javascript: 191 characters

The input format that I chose (within the rules) is the frequency numbers separated by commas. No spaces allowed and no newlines. The initial N must not be given. Each number must be just a serie of at least one [0-9] digits with an optional dot somewhere within. If the input is malformed, the behaviour is undefined.

How it works:

The period of some integer frequency numbers is the GCD of these numbers. If the given numbers are not integer, it sucessively multiplies they by 10 until it gets everything as an integer number (this exploit the fact that the non-integer numbers are given in base 10). After calculating the GCD, it divides the result by the power of ten used to multiply the input numbers, and hence getting the overall frequency. Inverting this we get the period.
Note: I am pretty sure that now that I gave this answer, somebody will code the same in APL or J and beat it. :(

The code:

d=1,s=prompt().split(",");for(a in s){s[a]=parseFloat(s[a]);while(s[a]*d%1>0)d*=10}g=s[0]*d;for(a in s){u=g;v=s[a]*=d;p=2;q=1;while(u>=p&v>=p)if(u%p|v%p)p++;else{u/=p;v/=p;q*=p}g=q}alert(d/g)


Testing it:

Input: 50,10
Output: 0.1
Interpretation: One GIF blinks 10 times per second (period = 0.1s) and the other 50 times (period = 0.02s). So a combined GIF would repeat itself in 0.1 seconds.

Input: 2.7,3.4
Output: 10
Interpretation: One blinking at 2.7 times per second will blink 27 times in 10 seconds. One blinking 3.4 times per second will blink 34 times in 10 seconds. So, 10 seconds is a period, and since GCD(27,34)=1, it is the smallest.

Input: 4.8,7.2
Output: 0.4166666666666667
Interpretation: One blinking at 4.8 times per second and the other at 7.2 times per second, gives a frequency of 2.4 times per second, which is a period 0.41666... seconds.

Input: 0.6,12,7.9,4.33
Output: 100
Interpretation: Similar to second case. 60, 1200, 790 and 433 times each 100 seconds. The GCD of these numbers is 1.

Input: 400,200,25,350
Output: 0.04
Interpretation: The slowest is the 25 times per second, which is the overall frequency. 25 times per second is a period of 0.04 seconds.

Input: 440,200,35,360
Output: 0.2
Interpretation: In 0.2 seconds, we have 88, 40, 7 and 72 blinks.

• GCD? That's the greatest common divisor, so it would always be smaller than the frequencies. I think you mean LCM (least common multiple). Commented Feb 20, 2014 at 1:08
• @Quincunx No, it is the GCD. The total period is the LCM of the individual periods, not individual frequencies. Commented Feb 20, 2014 at 1:23
• Here's the APL: (⊃x÷z)×∨/z←{⍵×10}⍣{⍵≡⌈⍵}x←⎕ Commented Feb 20, 2014 at 1:40
• Would you run a test case with rational numbers or "real numbers" (in the computer science sense of the term)? I don't think an approach based on GCD will work. Commented Feb 20, 2014 at 1:43
• @DavidCarraher I messed frequency with period, but now I already fixed. Just changed the g/d to d/g. I will add some test cases. Commented Feb 20, 2014 at 1:50