Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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!

share|improve this question
1  
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
1  
@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
add comment

1 Answer 1

up vote 3 down vote accepted

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[#[[1]]^#[[2]] & /@ repr] == long
StringJoin@
  Flatten[Riffle[
    Riffle[Table[ ToString[#[[1]]], {#[[2]]}], "*"] & /@ 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"
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.