2
$\begingroup$

Nearly 20 years ago, I was sitting in a physics class in high school when a "dumb" question occurred to me:

If two pendulums with unknown (different) frequencies started oscillating at the same time and same initial phase, can't you determine their frequencies by observing how long it would take them to reach the same phase again?

I then discarded the question: Surely it had been asked and answered hundreds of years before by someone like Newton, and its answer was likely sitting in a college textbook somewhere.

But some years later in college, I realized that I had asked a question that was not about physics but was, in fact, entirely about integer factorization: If two pendulums of periods $7$ and $5$ start oscillating at time $0$, they will next meet at time $35$, time $70$, and any other time that is a product of $7$, $5$, and some other integer $k$ — and at no other times in between.

So I expressed that as a simple relation, as an attempt to find $x$ in this expression:

$$\sin 2 \pi x = \sin 2\pi \frac{k}{x} = 0$$

That turned out to be a particularly bad form for any meaningful study, so some months later I reformulated it as this:

$$\cos (2\pi x) \cos (2\pi\frac{k}{x}) = 1$$

That this is true only when $x$ is a factor of $k$ is relatively easy to demonstrate:

  • Given an integer $k$,
  • The first cosine is only $1$ when $x$ is an integer;
  • The second cosine is only $1$ when $\frac{k}{x}$ is an integer;
  • The product is only $1$ when both cosines are $1$;
  • And when $x$ is an integer, $\frac{k}{x}$ can only be an integer if $x$ is a factor of $k$;
  • Therefore, the product is only $1$ when $x$ is an integer factor of $k$.

In effect, the second cosine constrains the relationship between $k$ and $x$ to be "factors", the first cosine constrains $x$ to be integers, and the two together constrain $x$ to be integer factors of $k$.

That expression has some nice properties as an alternate definition for "integer factorization": It is well-defined for both positive and negative numbers, well-defined across the entire real number line, including for negative and fractional numbers, and it has an interesting hole at $0$.

There are also several variations that can be constructed using sine or cosine, addition or multiplication, and various constants. For example:

$$\cos (2\pi x) + \cos (2\pi\frac{k}{x}) - 2 = 0$$

What I find most interesting about all of these expressions is that they convert the problem of factoring an integer (a discrete mathematics problem) into the domain of finding the real-valued roots of a "simple" expression of one variable (a continuous mathematics problem).

I have attempted for years since then to see if anybody else has discovered and explored this formulation, but I've never found any references to it in literature or online. I've also tried to see if these forms would make factoring integers any easier, using all sorts of transformations and tricks (trig identities, other periodic functions, $e^{i\pi}+1=0$), but I never successfully used it to "solve" any part of the integer factorization problem. Perhaps someone else has.

So to that end, the question that has been burning a hole in my brain for years is simply this:

Is this expression well-known among those studying integer factorization and I've simply been reading all the wrong books and websites, or did I discover something new?

$\endgroup$
  • $\begingroup$ Applying trig to problems involving integers is nothing new; for example, $\left \lfloor{x}\right \rfloor = (x-0.5) - \frac{\arctan(\tan(\pi(x - 0.5)))}{\pi}$ (math.stackexchange.com/questions/389063/…) $\endgroup$ – rubberchicken Mar 21 '14 at 23:40
  • $\begingroup$ That's not what I asked: I'm well aware that you can reformulate a number of other discrete-math problems as continuous-math problems. I asked whether anyone knew of this specific family of trig expressions that were related to integer factorization, and hopefully offer a source to read up on them if they're already well-known. $\endgroup$ – Sean Werkema Mar 21 '14 at 23:58
  • $\begingroup$ You'd probably enjoy reading about the ingenenious mechanical sieving machines devised by Lehmer in the precomputer era, e.g. using bicycles chains, photoelectric devices, etc. Below are some general references. See here for links. $\endgroup$ – Bill Dubuque Mar 22 '14 at 0:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.