I Number of Integers (<N) divisible only by one power of 2

  • I
  • Thread starter Thread starter chaoticflow
  • Start date Start date
  • Tags Tags
    Integers Power
AI Thread Summary
The discussion revolves around counting integers less than N that are divisible only by one power of 2, specifically in relation to the expression k = d + n/d, where d is a divisor of n. It is established that for k to be prime and greater than 2, d must be even while n/d must be odd, limiting n/d to having only one power of two. Participants explore the prime factorization of n and the implications of different combinations of d and n to derive valid k values. There is a suggestion of using number theory and modular arithmetic to simplify the counting process, as brute force methods may be inefficient. The conversation highlights the complexity of the problem and the need for a clearer understanding of the variables involved.
chaoticflow
Messages
8
Reaction score
0
TL;DR Summary
Count all integers < N that are divisible only by one power of 2
Hi,

The original problem was : for a given number k = d + n/d, where d is a divisor of another number n, how many k <= N are prime?

When I looked at this problem, for k to be prime > 2, it has to be odd.

This implies d and n/d can't both be even or odd. If d = 2, then d is even and n/d has to be odd.

Thus, n/d can't have more than one power of two.

If I can work out how to count integers <= N that only have one power of two, I can then test for primality within those integers. Any help in working this out, or if you could point out a general direction I should be looking in will be greatly appreciated.

Thanks,
 
Mathematics news on Phys.org
All k,d and n are designated or only a part of them ?
 
I'm not sure what designated means here. Can you clarify?
 
Also, I've worked out the problem a bit more:

For n < N, n = p1^a1 * p2^a2 * p3^a3. ... and so on where pi are prime factors of n and ai are powers of pi.

We know the highest power of a prime factor, pi is ai_max = log(n) - where base of log is pi. I.e. ai_max = int(log(n,pi))

Thus, every valid number will have the form n = 2* p2^a2*p3^a3 ... and so on. I.e. if one has N = 100, possible primes that can generate a number are 2/3/5/7 with max powers 6/4/2/2.

This can give us a count of possible numbers as 1*(4+1)*(2+1)*(2+1) = 16.

However, there will be some numbers that are greater than N. I.e. 2 * 3^4 * 5^2 * 7^2.

A brute force solution would be to iterate through all combinations and reject those which give a number > N.

However, is there a better way to solve this?

It seems like I'm missing something here - there's probably a simpler solution that uses the mod function and number theory.
 
8=6+\frac{12}{6}=5+\frac{15}{5}=4+\frac{16}{4}=3+\frac{15}{3}=...
For designated k there are many possible d's and n's. I am not sure how I should treat them.

2=1+\frac{1}{1}
3=1+\frac{2}{1}=2+\frac{1}{1}
5=1+\frac{4}{1}=2+\frac{6}{2}=3+\frac{6}{3}=4+\frac{4}{4}
I am almost sure any prime number is expressed as form ##d+\frac{n}{d}##.
 
Last edited:
chaoticflow said:
Summary:: Count all integers < N that are divisible only by one power of 2

The original problem was : for a given number k = d + n/d, where d is a divisor of another number n, how many k <= N are prime?
I don't understand this. Say ##\dfrac{n}{d}=e##, so ##k=d+e##. Every number ##k## can be written like this in multiple ways. Hence this isn't a condition at all and the question comes down to: How many primes are less than ##N##? Answer ##\dfrac{N}{\log N}.##
 
Numbers that are divisible by 2 but not higher powers of 2? Isn't that just 2+4k, i.e. every 4th number?

Note that e.g. d=4, n=12 leads to k = 4+12/4 = 7 which is prime.

Every integer k can be expressed as d+n/d, e.g. by choosing n=d=k-1.

A problem statement that says "a given number k" and then asks for how many k something is true is strange.
 
Back
Top