- #1
Banshi
- 1
- 0
Hi guys! I got really stuck with a Discrete Mathematics homework in Integers and Algorithms.
I know it is not very clear due to lack of symbols. If anyone didn't understand some part of the exercise I would like to clarify it.
The exercise is the following :
Define for B, an integer > 1, the base B expansion fB(n) of n, an integer > 0, as the sequence of integers fB(n) = (n0, n1, . . . , n(k)) satisfying 0 <= n(i) < B for 0 <= i <= k, n(k) != 0, and n = Ʃ(n(i)Bpower(i)), i=0 to k.
An integer n > 0 is called B-palindromic if its base B expansion fB(n) = (n0, n1, . . . , n(k)) satisfies n(i) = n(k−i) for 0 <= i <= k (i.e. n(i) means n index i).
a. Prove or disprove the following statement:
Ʉ n > 0, Ǝ B > 1 such that n is B-palindromic.
Let B > 1 be fixed. A sequence of integers (n0, n1, . . . , n(k)) is B-compliant if 0 <= n(i) < B for 0 <= i <= k and n(k) != 0. For any L >= B and any B-compliant integer sequence N = (n0, n1, . . . , n(k)), the integer N(L) (i.e. N index L) is defined as N(L) = Ʃ(n(i)Lpower(i)), i=0 to k.
And the integer Ӣ(L) is defined as Ӣ(L) = Ʃ(n(k-i)Lpower(i)), i=0 to k. Here, Ӣ(L) stands for negation of N, index L.
b. Prove that for any L >= B and any B-compliant sequence N = (n0, n1, . . . , n(k))
it is the case that fL(N(L)) = (n0, n1, . . . , n(k)).
c. Find the smallest L >= B such that N(L) + Ӣ(L) is L-palindromic for all B-compliant integer sequences N.
- fB(n) = (n0, n1, . . . , n(k)) with 0 <= n(i) < B for 0 <= i <= k, n(k) != 0, and n = Ʃ(n(i)Bpower(i)), i=0 to k.
- An integer n > 0 is called B-palindromic if its base B expansion fB(n) = (n0, n1, . . . , n(k)) satisfies n(i) = n(k−i) for 0 <= i <= k.
- (n0, n1, . . . , n(k)) is B-compliant if 0 <= n(i) < B for 0 <= i <= k and n(k) != 0.
- For any L >= B and any B-compliant integer sequence N = (n0, n1, . . . , n(k)), the integer N(L) (i.e. N index L) is defined as N(L) = Ʃ(n(i)Lpower(i)), i=0 to k.
- Ӣ(L) = Ʃ(n(k-i)Lpower(i)), i=0 to k.
I don't even know how to start, if anyone could help me with this it would be awesome.
Thanks Guys.
I know it is not very clear due to lack of symbols. If anyone didn't understand some part of the exercise I would like to clarify it.
The exercise is the following :
Homework Statement
Define for B, an integer > 1, the base B expansion fB(n) of n, an integer > 0, as the sequence of integers fB(n) = (n0, n1, . . . , n(k)) satisfying 0 <= n(i) < B for 0 <= i <= k, n(k) != 0, and n = Ʃ(n(i)Bpower(i)), i=0 to k.
An integer n > 0 is called B-palindromic if its base B expansion fB(n) = (n0, n1, . . . , n(k)) satisfies n(i) = n(k−i) for 0 <= i <= k (i.e. n(i) means n index i).
a. Prove or disprove the following statement:
Ʉ n > 0, Ǝ B > 1 such that n is B-palindromic.
Let B > 1 be fixed. A sequence of integers (n0, n1, . . . , n(k)) is B-compliant if 0 <= n(i) < B for 0 <= i <= k and n(k) != 0. For any L >= B and any B-compliant integer sequence N = (n0, n1, . . . , n(k)), the integer N(L) (i.e. N index L) is defined as N(L) = Ʃ(n(i)Lpower(i)), i=0 to k.
And the integer Ӣ(L) is defined as Ӣ(L) = Ʃ(n(k-i)Lpower(i)), i=0 to k. Here, Ӣ(L) stands for negation of N, index L.
b. Prove that for any L >= B and any B-compliant sequence N = (n0, n1, . . . , n(k))
it is the case that fL(N(L)) = (n0, n1, . . . , n(k)).
c. Find the smallest L >= B such that N(L) + Ӣ(L) is L-palindromic for all B-compliant integer sequences N.
Homework Equations
- fB(n) = (n0, n1, . . . , n(k)) with 0 <= n(i) < B for 0 <= i <= k, n(k) != 0, and n = Ʃ(n(i)Bpower(i)), i=0 to k.
- An integer n > 0 is called B-palindromic if its base B expansion fB(n) = (n0, n1, . . . , n(k)) satisfies n(i) = n(k−i) for 0 <= i <= k.
- (n0, n1, . . . , n(k)) is B-compliant if 0 <= n(i) < B for 0 <= i <= k and n(k) != 0.
- For any L >= B and any B-compliant integer sequence N = (n0, n1, . . . , n(k)), the integer N(L) (i.e. N index L) is defined as N(L) = Ʃ(n(i)Lpower(i)), i=0 to k.
- Ӣ(L) = Ʃ(n(k-i)Lpower(i)), i=0 to k.
The Attempt at a Solution
I don't even know how to start, if anyone could help me with this it would be awesome.
Thanks Guys.