Problems & Puzzles: Problems

Problem 41 . Iso-Omega Integers

Francois Bergeron sent the following puzzle as a variation of the Problem 20 of these pages:

Is it always possible to find 2^k-1 consecutive integers that have exactly k prime factors, taking into account their multiplicities?

Let's define Omega(m) = a1+a2+, whenever the decomposition of m, into distinct prime factors, is m = p1^a1.p2^a2 ... ps^as.

More precisely, the problem is to find 2^k-1 consecutive integers (arranged here around their mean n): {n-a, ... ,n-1, n, n+1, ... , n+a}, with a=2^(k-1)-1, for each of which Omega takes the value k.

It is easy to see that this is best possible, since
any list of 2^k consecutive integers contains one integer that is divisible by 2^k. Except for the special case 2^k (easily dealt with), this particular member of the list is clearly divisible by some other integer, hence its Omega value is larger than k.

A little more thought leads to the observation that
the central value n (the mean) of this list of 2^k-1 integers should be of the form 2^(k-1).p for some prime p. In this case, we say that p is k-nice.

It is easy to see that if p is k-nice, it is automatically j-nice for all j less or equal to k. This can be used to look for solutions in small cases.

An ancillary question is
to characterize the density distribution of k-nice primes. Among the first 10,000 primes, there are 679 primes that are 2-nice, 3 that are 3-nice (the smallest being 52919), and none that are 4-nice.

Apparently, 12190527809 (found by Brian Trial, Ferndale, Michigan) is the smallest 4-nice prime.

Questions (theoretical 1, 2, & 3; computational 4)

  1. Demonstrate that the central value n (the mean) of a list of 2^k-1 iso-Omega integers, Omega=k, should be of the form 2^(k-1).p for some prime p
  2. Is it always possible to find 2^k-1 consecutive iso-Omega integers, Omega=k ?
  3. How would you study the characterization of the density distribution of the k-nice primes?
  4. Find the smallest 5-nice prime (you may send your best approximation to it)

J. K. Andersen, Joseph L. Pe and David Terr solved the question 1 of this puzzle. Let's see the Terr's argument completely similar to the Andersen's one:

The central value must be divisible by 2^(k-1) since it's 2^(k-1) away from each endpoint, each of which is divisible by 2^k. Thus it has the form 2^(k-1)m. But m must be prime in order to have the number of factors counting multiplicities equal k.





Records   |  Conjectures  |  Problems  |  Puzzles