# How to represent very long integers with at-most-8-digit(base-10) short integers with * and +

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:

29427736469514379027531261659072347
58899562724319710108573382000184640
1732944474195510410991057714955859184


Is there any Mathematica implementation of such algorithm?

Thanks!

• 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? – Nasser Nov 29 '13 at 1:32
• @Nasser sometimes "decimal digits" is used to make it clear base-10 is used to count digits – ssch Nov 29 '13 at 1:34
• @Nasser ssch, thanks. I mean base-10 integers – 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
StringJoin[
MapIndexed[
If[First@#2 > 1, "+", ""] <> ToString[#1 ] <>
Table[ "*" <> ToString[ base], {First@#2 - 1}] &, Reverse@ repr]]

(*
613921084644306481276815940460
True
"3623623532+1291570358*4294967296+3215957613*4294967296*4294967296+7*4294967296*4294967296*4294967296"
*)


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[#[]^#[] & /@ repr] == long
StringJoin@
Flatten[Riffle[
Riffle[Table[ ToString[#[]], {#[]}], "*"] & /@ repr , "+"]]

(*
49745600692119322339
True
"83982*83982*83982*83982+104024*104024*104024+149275*149275+17914"
*)


first approach for this number and base gives:

   "760108+183469*999999+745749*999999*999999+49*999999*999999*999999"