I need an algorithm in Mathematica, which can represent any very long integer, prime or not, into the the product operation "*" and sum "+" forms by short integers (not more than 8 decimal digits).

Additional rules on the final expression of the very long integer are:

(1). the lengths (base-10 decimal digits) of all short prime integers employed should be as close to 6 as possible, the closer the better;

if there are n different short integers used, we use the sum of squared differences between their lengths and 6 as the criterion: the smaller the better (first priority);

(2). the less "+" operators used the better (second priority); the less "*" the better(the third priority).

The final expression of the integer should be usable immediately in C/C++.

Example numbers for testing:


Is there any Mathematica implementation of such algorithm?


  • 1
    $\begingroup$ short integers (not more than 6 decimal digits). Can you clarify this with an example? How can an integer have decimal digits? something with decimal point is not an integer, right? or are you using different notations? $\endgroup$ – Nasser Nov 29 '13 at 1:32
  • 1
    $\begingroup$ @Nasser sometimes "decimal digits" is used to make it clear base-10 is used to count digits $\endgroup$ – ssch Nov 29 '13 at 1:34
  • $\begingroup$ @Nasser ssch, thanks. I mean base-10 integers $\endgroup$ – LCFactorization Nov 29 '13 at 1:41

Not sure if this is what you are after but maybe if its not it will help you clarify the question:

long = RandomInteger[10^30];
base = 2^32;
repr = IntegerDigits[long, base];
Total@MapIndexed[ #1 base^(First@#2 - 1) &, Reverse@ repr] == long 
      If[First@#2 > 1, "+", ""] <> ToString[#1 ] <> 
        Table[ "*" <> ToString[ base], {First@#2 - 1}] &, Reverse@ repr]]


I see you asked for 6 digits max , just make the base smaller..

Edit: alternate approach that tries to use mostly large numbers..

long = RandomInteger[10^20]
base = 999999;
reduce[ long_ /; long > base] :=
  Module[{n = Ceiling[Log[long]/Log[base]], p1},
          {#, n, reduce[long - #^n]} &@Floor[long^(1/n)]]
reduce[ long_] := {long, 1};
repr = Partition[Flatten@reduce[long], 2];
Total[#[[1]]^#[[2]] & /@ repr] == long
    Riffle[Table[ ToString[#[[1]]], {#[[2]]}], "*"] & /@ repr , "+"]] 


first approach for this number and base gives:


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.