Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Has anyone discovered a way of coding a sequence of natural numbers into a natural number by map $f$ that has the following property $f(k_1, .., k_n) + f(k_{n+1}, .., k_{2n}) = f(k_1 + k_{n+1}, .., k_n + k_{2n})$? ($k_1$ and so on are natural numbers and $f$ codes any sequence of natural numbers into a unique natural number.)

Add: Let us say that we limit $n$ to be a particular number. So if we set $n$ to be 3, there cannot be $f$ that accepts one number only and so on.

Add 2: Every number received by $f$ is treated as numbers, not sequences.

share|improve this question
    
But any such $f$ must satisfy $f(f(1,1))=f(1,1)f(1)=f(f(1),f(1))$, so $f$ cannot satisfy the additive property and code any sequence into a unique natural number simultaneously. –  Ivan Loh Mar 19 '13 at 3:40
    
For $n=1$, take $f(n)=n$. For fixed $n>1$, @Alex Kruckman has answered it completely. –  Ivan Loh Mar 19 '13 at 3:50
    
No, but then I added that let us assume that $f$ only takes $n$ numbers; it does not take less than $n$ number or more than $n$ numbers. –  Maps from subways Mar 19 '13 at 4:29
add comment

1 Answer

Such a coding is impossible for $n>1$.

Let $a = (1,0,\dots,0)$ and let $b = (0,1,0,\dots,0)$.

When I write $m \cdot a$ for a natural number $m$ and a vector $a$, I mean $a + \dots + a$ (added $m$ times).

Now $a$ is coded by a natural number $m_a = f(a)$ and $b$ is coded by a natural number $m_b = f(b)$. But:

\begin{align} f(f(b),0,\dots,0) &= f(m_b\cdot a)\\ &= m_b\times f(a)\\ &= m_a\times f(b)\\ &= f(m_a\cdot b)\\ &= f(0,f(a),0,\dots,0) \end{align}

...which shows that the coding is not injective, since $(0,f(a),0,\dots,0)\neq (f(b),0,\dots,0)$, unless $f(a) = f(b) = 0$ but then again we have that the coding is not injective, since $a\neq b$.


Edited: Maybe an explicit example will help you see what's going on. Let's take $n = 2$ and say for example that $f(1,0) = 3$, $f(0,1) = 5$. Then:

\begin{align} f(5,0) &= f(1 + 1 + 1 + 1 + 1, 0 + 0 + 0 + 0 + 0)\\ & = f(1,0) + f(1,0) + f(1,0) + f(1,0) + f(1,0)\\ & = 3 + 3 + 3 + 3 + 3\\ & = 15\\ & = 5 + 5 + 5 \\ &= f(0,1) + f(0,1) + f(0,1) \\ &= f(0+0+0,1+1+1) \\ &= f(0,3) \end{align}

If you compare these steps with my argument above, you'll see that it's exactly the same, except $3$ is $m_a$ and $5$ is $m_b$.

share|improve this answer
    
But what if we do not allow $f$ to receive only one number? Assume that we don't use the coded number to another function; every number received by $f$ is treated as numbers, not sequences. –  Maps from subways Mar 19 '13 at 4:30
    
Can you explain your comment further? In what I've written, I've always treated $f$ as a function $\mathbb{N}^n\rightarrow\mathbb{N}$, that is, I've only applied $f$ to sequences of length $n$. –  Alex Kruckman Mar 19 '13 at 4:32
    
But $1, 0, 0, \ldots , 0$ is a sequence of $n$ natural numbers. What is wrong with that? –  Ivan Loh Mar 19 '13 at 4:33
    
What I mean is, $f(f(b), 0, ..., 0) = f(m_b \cdot a)$ part. So, $f(f(b), 0, ..., 0) = f(m_b, 0, ..., 0)$. And as $a$ represents $(1, 0, ..., 0)$, this is used to equal to $f(m_b \cdot a)$. But while $a$ does represent $(1, 0, ..., 0)$, I want $f$ to disallow one-number input case. So $f(m_b \cdot a)$ is not allowed, and any numbers (input) in $a$ are treated as numbers, not sequences. –  Maps from subways Mar 19 '13 at 4:58
    
Oh, I saw the edited part now. I'll have a look at it and respond again. Thanks. –  Maps from subways Mar 19 '13 at 5:01
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.