# Avoid MemoryAllocationFailure in code with big list

I wrote some code that should find number k (10 digits long), where each digit (0-9) is used only once and satisfying the following conditions:

• The first digit of k should be divisible by 1 (duh)
• The first two digits of k should be divisible by 2
• ...
• The first ten digits of k should be divisible by 10

Here is the code:

k = Table[i, {i, 0, 9999999999}];
Select[%, IntegerLength[#, 10] == 10 &];
Select[%, Divisible[#, 10] &];
Select[%, Divisible[IntegerPart[#/10], 9] &];
Select[%, Divisible[IntegerPart[#/100], 8] &];
Select[%, Divisible[IntegerPart[#/1000], 7] &];
Select[%, Divisible[IntegerPart[#/10000], 6] &];
Select[%, Divisible[IntegerPart[#/100000], 5] &];
Select[%, Divisible[IntegerPart[#/1000000], 4] &];
Select[%, Divisible[IntegerPart[#/10000000], 3] &];
Select[%, Divisible[IntegerPart[#/100000000], 2] &]


Unfortunately I got an error: SystemException["MemoryAllocationFailure"]

What can I do to avoid this error? Is there a more neat way to solve my problem in Mathematica?

Thanks a lot!

EDIT: I am a real beginner with Mathematica, so even basic tips for improvement are appreciated!

The original brute force approach is also fine, provided the initial candidate list is better chosen:

k = 10*Map[FromDigits, Permutations[Range]];
Select[%, Divisible[IntegerPart[#/10], 9] &];
Select[%, Divisible[IntegerPart[#/100], 8] &];
Select[%, Divisible[IntegerPart[#/1000], 7] &];
Select[%, Divisible[IntegerPart[#/10000], 6] &];
Select[%, Divisible[IntegerPart[#/100000], 5] &];
Select[%, Divisible[IntegerPart[#/1000000], 4] &];
Select[%, Divisible[IntegerPart[#/10000000], 3] &];
Select[%, Divisible[IntegerPart[#/100000000], 2] &]

(* {3816547290} *)


The above can also be written in a more compact way as

Fold[Function[{l, d}, Select[l, Divisible[IntegerPart[#/10^d], 10 - d] &]], k, Range]

• Interesting! Why does that require less memory? – GambitSquared Jun 30 '17 at 21:27
• There are only 362880 integers in k, thanks to the condition that each digit is used just once. – ilian Jun 30 '17 at 21:30

You can construct such number starting from the most significant digits.

First, find all possible highest digits, then all possible combinations of highest two digits and so on...

iFindNextDigit[digits_List]:= Module[
{newdigits, candidateNumbers, result},
newdigits = Complement[Range[0,9], digits];
candidateNumbers = Map[Join[digits, {#}]&, newdigits];
result = Select[candidateNumbers, (Divisible[FromDigits[#], Length[digits]+1] )&];
If[result == {}, Nothing, result]
];

findNextDigit[x_]:=Flatten[Map[iFindNextDigit,x],1];

Nest[findNextDigit, iFindNextDigit[{}], 9]


{{3, 8, 1, 6, 5, 4, 7, 2, 9, 0}}

This solution uses 0.06 MB of memory according to MaxMemoryUsed. Your original solution will need more than 80 GB of RAM to run.

• The first solution is not correct because 965 is not divisible by 3. The second solution is not correct because 95 is not divisible by 2... – GambitSquared Jun 30 '17 at 21:00
• I have changed the solution to match your definition of the first digits. – Shadowray Jun 30 '17 at 21:08

To resolve similar issues, i have increased the Java heap size using the following in my "init.m" file:

    <<JLink;
InstallJava[];
ReinstallJava[JVMArguments -> "-Xmx512m"];
`

Does that work for you?

• This computation does not involve Java in any way, so increasing the heap size is unlikely to help. – ilian Jul 2 '17 at 1:35
• Yeah. I was just thinking of the error message and not the root cause. Doh! – xsk8rat Jul 2 '17 at 14:41