Intereting Posts

Show adding rows to a non-singular square matrix will keep or increase its minimum singular value
How can I prove the formula for calculating successive entries in a given row of Pascal's triangle?
Defining/constructing an ellipse
Find all entire $f$ such that $f(f(z))=z$.
Do Incomplete Normed Vector Spaces Whose Duals Are Reflexive Exist?
Is it possible to find an infinite set of points in the 3D space where the distance between any pair is rational?
Symmetric Icon Fractals
Best way to integrate $ \int_0^\infty \frac{e^{-at} – e^{-bt}}{t} \text{d}t $
Show that $\{1, \sqrt{2}, \sqrt{3}\}$ is linearly independent over $\mathbb{Q}$.
A module is projective iff it has a projective basis
For integers $a$ and $b$, $ab=\text{lcm}(a,b)\cdot\text{hcf}(a,b)$
math fallacy problem: $-1= (-1)^3 = (-1)^{6/2} = \sqrt{(-1)^6}= 1$?
The kernel of an action on blocks, specifically the action on the orbits of normal subgroup
$\sqrt{7\sqrt{7\sqrt{7\sqrt{7\sqrt{7\cdots}}}}}$ approximation
We all use mathematical induction to prove results, but is there a proof of mathematical induction itself?

An integer $m$ is **acceptable** iff in it’s decimal representation all digits are different. For example $9876543210$ is the largest acceptable integer. For each $n\in \Bbb N$, $\theta(n)$ is the number of all acceptable positive integers not greater than $n$.

Is there a simple formula for $\theta(n)$?

- Find the largest number having this property.
- Did I derive a new form of the gamma function?
- Useless math that become useful
- Is the Collatz conjecture in $\Sigma_1 / \Pi_1$?
- Decomposing a circle into similar pieces
- “Canceling Out The Zeroes” In A Mathematically Sane Way $\frac{0\times x}{0\times 1}$

- Square of digit reversal equals digit reversal of square?
- If $abc=1$, then $\frac{a^{n+2}}{a^n+(n-1)b^n}+\frac{b^{n+2}}{b^n+(n-1)c^n}+\frac{c^{n+2}}{c^n+(n-1)a^n} \geq \frac{3}{n} $
- Is $2^{16} = 65536$ the only power of $2$ that has no digit which is a power of $2$ in base-$10$?
- Does there exist a positive integer $n$ such that it will be twice of $n$ when its digits are reversed?
- Ten soldiers puzzle
- 5 geometric shapes, all touching each other
- A further question to “does-there-exist-a-tool-to-construct-a-perfect-sine-wave”
- Two players placing coins on a round table with the goal of making the last move

This is not a math answer, but if you’re only interested in the results I guess my approach is much simpler to understand. I simply let the computer calculate the numbers.

This one works, but is slow:

```
def isAcceptable(number):
s = str(number)
for i in range(len(s)-1):
for j in range(i+1,len(s)):
if s[i] == s[j]:
return False
return True
def getNumberOfAcceptableNumbers(n):
acceptable = 0
i = 1
while i <= n:
if isAcceptable(i):
acceptable += 1
i += 1
return acceptable
print(getNumberOfAcceptableNumbers(98765432))
```

It took over 5 minutes on my machine for 98765432. The result was 2,345,850.

I’m currently implementing this in Java. For 98765432 it takes only 32 seconds and I’m currently improving it.

```
import java.math.BigInteger;
public class DiffDigits {
/**
* All numbers that are not acceptable have at least one pair of two
* indices that have the same digit. Take the pair where the lower
* index is maximal. Return the lower index.
*
* @param number
* @return -1 iff number is acceptable, otherwise index as described above
*/
public static int getHighestIndexThatHasToChange(BigInteger number) {
String s = number.toString();
// i == 0 is the most significant digit
for (int i = 0; i < s.length() - 1; i++) {
for (int j = i + 1; j < s.length(); j++) {
if (s.charAt(i) == s.charAt(j)) {
return j;
}
}
}
return -1;
}
/**
* Get the amount of positive integers that are acceptable in range [i, end]
*
* @param i the first number to check
* @param end the last one to check
* @return
*/
public static int getNumberOfAcceptableNumbers(BigInteger i, BigInteger end) {
BigInteger one = new BigInteger("1");
BigInteger ten = new BigInteger("10");
int acceptable = 0;
while (i.compareTo(end) <= 0) {
int highestIndex = getHighestIndexThatHasToChange(i);
if (highestIndex == -1) {
acceptable++;
i = i.add(one);
} else {
i = i.add(ten.pow(i.toString().length() - 1 - highestIndex));
}
}
return acceptable;
}
public static void main(String[] args) {
System.out.println("Start");
long startTime = System.nanoTime();
System.out.println(getNumberOfAcceptableNumbers(new BigInteger("1"),
new BigInteger("9876543210")));
long endTime = System.nanoTime();
long duration = endTime - startTime;
System.out.println("Execution took " + duration / 1000000000.0
+ " seconds.");
System.out.println("End");
}
}
```

For $n = 9876543210$ there are 8,877,690 acceptable numbers. For this range, it took 56 seconds to execute. For every other range it will be less.

By the way, this sounds like a Project Euler task. Is it one? Which task is it?

Quite often, counting questions that are trivial for $n \le 10^d$ can be solved very efficiently in general by decomposing into decimal blocks of size $m\cdot 10^d$.

Define $\psi(n) = \theta(n-1)$ for convenience, and say you want to know $\psi(4537)$: decompose this into $$\psi(1000) + [\psi(4000)-\psi(1000)] + [\psi(4500)-\psi(4000)] + [\psi(4530)-\psi(4500) ] + [\psi(4537) – \psi(4530)].$$

Previous answers have already shown how to calculate $\psi(1000)$, but each of the remaining blocks is equally simple. For instance, $[\psi(4500)-\psi(4000)]$ is just the number of acceptable numbers between $4000$ and $4499$, inclusive. In this block the first digit is fixed, and the second digit is any of $0,1,2,3$ ($4$ being forbidden). The third digit has $8$ choices, and the fourth digit has $7$, so $\psi(4500)-\psi(4000) = 4\cdot8\cdot 7$.

The other blocks follow a quite similar pattern, they can all be computed using nothing more than “count how many digits of $x$ are at most $y$” and testing for distinctness, all very efficient operations even for bases much, much larger than $10$.

Yes. See this OEIS page or this MathWorld page.

$$ \theta(10^n – 1) = \sum_{k=1}^n \frac{9 \cdot 9!}{(10 – k)!} $$

- The first digit may be any of {1,2,…,9}, so 9 choices.
- The second digit may be any digit of {0,1,…,9}, except the first one. So 9 choices.
- The third digit may be any digit of {0,1,…,9}, except the first and the second one. So 8 choices.
- …
- The tenth digit may be any digit of {0,1,…,9}, except the nine previous,. So 1 choice.
- It is not possible to have 11 distinct digits.

So $θ(n)=9 \times 9 \times 8\times 7 … \times (10-n) = 9 \times \frac 9! {(-n)!}$

Apart for the $θ(n)=0$ for $n>10$ already mentioned, you also have an exception for 0, $θ(0)=10$ since $0$ is acceptable.

- Show that $15\mid 21n^5 + 10n^3 + 14n$ for all integers $n$.
- Define a Principal Branch in Complex Analysis
- How to prove these two random variables are independent?
- Fixed field of automorphism $t\mapsto t+1$ of $k(t)$
- Is taking projective closure a functor?
- Subspaces of a tensor product of vector spaces
- Show that $X$ can be represented as a union of disjoint equivalence classes
- Choose 100 numbers from 1~200 (one less than 16) – prove one is divisible by another!
- Projectivity of $B$ over $C$, given $A \subset C \subset B$
- Proving $x\leq \tan(x)$
- How many zeros are there at $1000!$ in the base $24$
- In arbitrary commutative rings, what is the accepted definition of “associates”?
- Order of $GL(n, \mathbb Z_p)$
- For a compact covering space, the fibres of the covering map are finite.
- Is symmetric group on natural numbers countable?