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

[chaoticflow]

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,

 

[anuttarasammyak]

All k,d and n are designated or only a part of them ?

 

[chaoticflow]

I'm not sure what designated means here. Can you clarify?

 

[chaoticflow]

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.

 

[anuttarasammyak]

$$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}$.

 

[fresh_42]

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}.$

 

[mfb]

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.