Finding 10-Digit Numbers with Divisibility Rules

[micromass]

Find all 10-digit numbers $a_1a_2a_3a_4a_5a_6a_7a_8a_9a_{10}$ (for example, if $a_1= 0$, $a_2$ = 1, $a_3 = 2$ and so on, we get the number 0123456789), such that all the following hold:

- The numbers $a_1,~a_2,~a_3,~a_4,~a_5,~a_6,~a_7,~a_8,~a_9,~a_{10}$ are all distinct
- 1 divides $a_1$
- 2 divides $a_1a_2$
- 3 divides $a_1a_2a_3$
- 4 divides $a_1a_2a_3a_4$
- 5 divides $a_1a_2a_3a_4a_5$
- 6 divides $a_1a_2a_3a_4a_5a_6$
- 7 divides $a_1a_2a_3a_4a_5a_6a_7$
- 8 divides $a_1a_2a_3a_4a_5a_6a_7a_8$
- 9 divides $a_1a_2a_3a_4a_5a_6a_7a_8a_9$
- 10 divides $a_1a_2a_3a_4a_5a_6a_7a_8a_9a_{10}$

If you find this too easy: generalize this to to other bases.

 

[drizzle]

*blank stare*

Is this a joke?

 

[micromass]

*blank stare*

Is this a joke?

Do you find it funny?

 

[AnTiFreeze3]

Do you find it funny?

 

[jbunniii]

Clearly we must have $a_{10} = 0$ and $a_5 = 5$.

$a_2, a_4, a_6, a_8$ are all even, so they must be 2,4,6,8 in some order.

Therefore, because we can't re-use digits, $a_1, a_3, a_7, a_9$ must be 1,3,7,9 in some order.

Since $a_3$ is odd, the constraint that 4 divides $a_1 a_2 a_3 a_4$ implies that $a_4$ must be 2 or 6.

Similarly, since $a_7$ is odd, the constraint that 8 divides $a_1 a_2 a_3 a_4 a_5 a_6 a_7 a_8$ implies that $a_8$ must be 2 or 6.

Therefore, $a_4$ and $a_8$ must be 2 and 6 in some order.

It follows that $a_2$ and $a_6$ must be 4 and 8 in some order.

I would continue but it's making me tired.

 

[drizzle]

Do you find it funny?

I'm questioning how well educated you are?

 

[mfb]

Extending jbunniii's analysis:
Numbers in brackets refer to the corresponding condition, e.g. (1) is "1 divides a₁".
From (3) and (6), we get that $a_4+5+a_6$ is divisible by 3.
If a_4=2, then a_6=8. In addition, a_8=6, and therefore a_2=4. I will call this case A.
If a_4=6, then a_6=4. In addition, a_8=2, and therefore a_2=8. I will call this case B.

Case A: X4X258X6X0
Case B: X8X654X2X0

This allows a better analysis of (8): We know that a_6 is even, so a_7=1 mod 4 (case A) // a_7=3 mod 4 (case B).
Case A: a_7=1 or a_7=9
Case B: a_7=3 or a_7=7

Using (9) and (6) (where (9) is trivial after (10) was used), $a_7+a_8+a_9$ is divisible by 3.
Case A: One out of (1,7) and 9 is used for a_7 and a_9.
Case B: 7 cannot be used, so a_7=3 and a_9=1.

Case B: X8X6543210
Well... we just have (7) left to analyze, but none of the two remaining options lead to a solution. Too bad, would have given a nice pattern!

So we have to split case A into subcases:

AA: a_7=1, a_9=9
AB: a_7=9, a_9=1
AC: a_7=9, a_9=7

Looking at (7) again, we get

Spoiler

3472581690 as the only solution
This line increases the spoiler size so it is not obvious to see that there is just one solution.

Some steps towards a generalization:
The last digit is always zero, and the first condition is always true.
The sum of all digits in base b is b(b-1)/2, this is divisible by (b-1) for even b only. Therefore, no odd base has a solution. In even bases, (b-1) is trivially satisfied. The even/odd split for the numbers is true in all (even!) bases.

base 2 gives 10 as trivial solution.
base 4 has only trivial conditions, and both 1230 and 3210 are solutions.
base 6 gives 143250 and 543210 as solutions.
base 8: after evaluating (4) and (6), I get xxx4xx30.
Edit: With ugly casework, I get 16547230, 72145630, 76541230 for base 8.

 

[Caracrist]

mfb, you have mistakes...
347 is not divided by 3 for example


The answer is:

Spoiler

Base 2: 10
Base 4: 1230, 3210
Base 6: 143250, 543210
Base 8: 32541670, 52347610, 56743210
Base 10: 3816547290
Base 14: 9C3A5476B812D0

I am not sure, but it looks like no other base has any solution.

 

[mfb]

Oh, I messed up the combination of (9) and (6) in both cases.

I can confirm your solutions up to base 14.
My python hack is too slow to search for solutions beyond base 16.