2
$\begingroup$

We say that $N$ is writable as a sum of permutation pair $\{a,b\}$ if $a+b=N$, $a\neq b$ and $a$ and $b$ are permutations of each other (e.g. $321 = 156 + 165 = 147 + 174 = ... $).

Looking at 3-digit numbers, 386 of them are writable as a sum of permutations.

  1. What is the density of numbers which are writable as a sum of permutations? Does it go to $1$ as $N$ increases?

Another interesting question is the number of different permutations that a number can be written as.

Looking at 3 digit numbers:

  • $321$ is writable as sum of 5 different permutation pairs.
  • $666$ is writable as sum of 7 different permutation pairs.
  • $888$ is writable as sum of 10 different permutation pairs.

And for 4 digits:

  • $5555$ is writable as sum of 28 different permutation pairs.
  • $7777$ is writable as sum of 58 different permutation pairs.
  • $9999$ is writable as sum of 96 different permutation pairs.

2.What is the best upper bound we can give on the number of different number permutation pairs that sums up to $N$? ($\frac{N}{2}$ is trivial, is there a better bound?)

$\endgroup$
  • 1
    $\begingroup$ Surely every even number is a sum of a permutation pair; $2n=n+n$ --- the identity is a permutation! If you mean to exclude the identity permutation, you should explicitly say so in the body of the question. $\endgroup$ – Gerry Myerson Sep 1 '14 at 13:04
  • $\begingroup$ @GerryMyerson - You are correct, I meant different a,b, I'll edit the question, thanks. $\endgroup$ – R B Sep 1 '14 at 13:09
  • $\begingroup$ Do you allow leading zeroes? E.g., $101=100+001$? $\endgroup$ – Gerry Myerson Sep 2 '14 at 3:12
  • $\begingroup$ @GerryMyerson - yes, leading zeros are fine. $\endgroup$ – R B Sep 2 '14 at 5:48
  • 1
    $\begingroup$ Then aren't there more than 10 pairs for 888? $840+048,741+147,642+246,543+345,804+084,714+174,624+264,534+354,480+408,471+417,462+426,453+435$ $\endgroup$ – Gerry Myerson Sep 2 '14 at 6:45
0
$\begingroup$

If carry is not allowed, better bound would be $5* 9^{\lceil log_{10}^n\rceil - 1}$ + some delta. But, what happens when carry is there in addition?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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