Solving Discrete Math: Integer & Algorithm Homework

[Banshi]

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 :

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.

 

[Stephen Tashi]

I've attempted to rewrite your problem by condensing it and using LaTex. Perhaps someone who can do number theory will be happier with this version.

1. The problem statement

a. Prove or disprove the following statement: For each integer $$n > 0$$ there exists a base $$B > 1$$ so that $$n$$ is palandromic when written in base $$B$$..

b. Prove that for any $$L \geq B$$ and any $$B-$$compliant sequence $$\{N\} = \{n_0, n_1, . . . , n_k) \}$$ it is the case that the expansion of $$N$$ to the base $$L$$, $$\{f_L(N(L))\} = \{n_0, n_1, . . . , n_k\}$$.

c. Find the smallest $$L \geq B$$ such that $$N_L + \tilde{N}_L$$ is $$L-$$ palandromic for all $$B-$$compliant integer sequences $$\{N\}$$


2. Relevant definitions

Define the base $$B$$ expansion $$f_B(n)$$ of an integer $$n > 0$$ to be the sequence of integers $$\{f_B(n)\} = \{n_0, n_1,...,n_k\}$$ satisfying $$0 \leq n_i < B$$ for $$0 \leq i \leq k$$ with $$n_k \neq 0$$ and $$n = \sum_{i=0}^k n_i B^i$$

An integer $$n > 0$$ is palindromic when written in base $$B$$ means that $$\{f_B(n)\} = \{n_0, n_1, . . . , n_k \}$$ satisfies $$n_i = n_{k-i}$$ for $$0 \leq i \leq k$$

Let $$B > 1$$ be fixed. A sequence of integers $$\{n_0, n_1, . . . , n_k\}$$ is $$B$$-compliant if $$0 \leq n_i < B$$ for $$0 <= i <= k$$ and $$n_k \neq 0$$.

For any $$L \geq B$$ and any $$B$$-compliant integer sequence $$N = \{n_0, n_1, . . . , n_k\}$$, the integer $$N(L)$$ is defined as $$N(L) = \sum_{i=0}^ k n_i L^i$$.
And the integer $$\tilde{N}(L)$$ is defined as
$$\tilde{N}(L) = \sum_{i=0}^k n(k-i)L^i$$.


If you use LaTex, be advised that there is a bug in the way LaTex is cached on this forum. When composing a post, you must use the "preview" feature of the editor and, after the page appears, you must use the "reload" feature of your browser to display the page again. A similar procedure must be used when you edit one of your posts. Before pages are reloaded, the LaTex may look nonsensical or not reflect your edits.

 

[jaiez]

I have these two questions in discrete mathematics and I need your help to answer it….
Proof that ∀x⇁p(x)≡⇁∃x p(x)
And
Proof that ⇁∀xp(x)≡∃x⇁ p(x)
Let R be the relation on the set {1,2,3,4,5} containing the order pairs(1,1) ,(1,2) (1,3) ,(2,3) (2,4) ,(3,1) (3,4) ,(3,5) ,(4,2) (4,5) ,(5,1) (5,2) ,and(5,4),Find
R^3
R^4
R^5