3
$\begingroup$

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!

$\endgroup$
4
$\begingroup$

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

k = 10*Map[FromDigits, Permutations[Range[9]]];
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[8]]
$\endgroup$
  • $\begingroup$ Interesting! Why does that require less memory? $\endgroup$ – GambitSquared Jun 30 '17 at 21:27
  • 1
    $\begingroup$ There are only 362880 integers in k, thanks to the condition that each digit is used just once. $\endgroup$ – ilian Jun 30 '17 at 21:30
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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... $\endgroup$ – GambitSquared Jun 30 '17 at 21:00
  • $\begingroup$ I have changed the solution to match your definition of the first digits. $\endgroup$ – Shadowray Jun 30 '17 at 21:08
0
$\begingroup$

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

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

From Wolfram Support and Stack Exchange as well.

Does that work for you?

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

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.