Explore BrainMass

Binary Representations and Prime Factors

1- For n belongs to N (set of natural numbers) let B(n) denote the number of digits used in the binary representation of n. For example
B(1) = 1;
B(2) = 2;
B(3) = 2;
B(4) = 3:

Find a closed formula for B(n) for an arbitrary n belongs to N.

2: Prove that if gcd(a, b) = d then a/d and b/d are relatively prime.

3- Find the smallest prime factor of (p1)(p2)...(pk) +1, where p1, p2, ... pk are the kth smallest primes for all positive integers k not exceeding 50.

Solution Preview

1. B(n) is the smallest integer which is greater than or equal to log(base 2) n.
In another word, we can find some integer k, such that 2^(k-1)<n<=2^k, then B(n)=k.

2. Proof: if a/d and b/d are not relatively prime, then they have a common factor r>1. Then
we have a/d=rx, ...

Solution Summary

Binary Representations and Prime Factors are investigated.