Solved

Task on number theory

Posted on 2014-10-21
13
167 Views
Last Modified: 2014-12-20
Two factors
   Which the least number n can we imagine in product n = a∙b like k ways? Products a∙b and b∙a is one of the way, where all numbers is natural (1≤ k ≤50).

   Input
   One number k.
   Output
   One number n.

Could you describe the algorithms. I have one complicated algro using the first theorem of arithmetics, but it can't pass a few tests.
0
Comment
Question by:Nusrat Nuriyev
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 8
  • 5
13 Comments
 
LVL 84

Expert Comment

by:ozo
ID: 40396219
If the prime factorization of  n is
p_0^a_0 * p_1^a_1 * ... * p_n^a_n
then the number of ways to write it as n = a∙b, where a∙b and b∙a are the same, would be
ceiling( (a_0+1)*(a_1+1)*...*(a_n+1) / 2 )
0
 
LVL 84

Expert Comment

by:ozo
ID: 40396352
So the least n for 1≤ k ≤50 seem to be
k           n
1(1)      1=()
2(3)      4=(2^(3-1))
3(6)      12=(2^(3-1)*3^(2-1))
4(8)      24=(2^(4-1)*3^(2-1))
5(9)      36=(2^(3-1)*3^(3-1))
6(12)      60=(2^(3-1)*3^(2-1)*5^(2-1))
7(14)      192=(2^(7-1)*3^(2-1))
8(16)      120=(2^(4-1)*3^(2-1)*5^(2-1))
9(18)      180=(2^(3-1)*3^(3-1)*5^(2-1))
10(20)      240=(2^(5-1)*3^(2-1)*5^(2-1))
11(21)      576=(2^(7-1)*3^(3-1))
12(24)      360=(2^(4-1)*3^(3-1)*5^(2-1))
13(25)      1296=(2^(5-1)*3^(5-1))
14(27)      900=(2^(3-1)*3^(3-1)*5^(3-1))
15(30)      720=(2^(5-1)*3^(3-1)*5^(2-1))
16(32)      840=(2^(4-1)*3^(2-1)*5^(2-1)*7^(2-1))
17(33)      9216=(2^(11-1)*3^(3-1))
18(36)      1260=(2^(3-1)*3^(3-1)*5^(2-1)*7^(2-1))
19(38)      786432=(2^(19-1)*3^(2-1))
20(40)      1680=(2^(5-1)*3^(2-1)*5^(2-1)*7^(2-1))
21(42)      2880=(2^(7-1)*3^(3-1)*5^(2-1))
22(44)      15360=(2^(11-1)*3^(2-1)*5^(2-1))
23(45)      3600=(2^(5-1)*3^(3-1)*5^(3-1))
24(48)      2520=(2^(4-1)*3^(3-1)*5^(2-1)*7^(2-1))
25(50)      6480=(2^(5-1)*3^(5-1)*5^(2-1))
26(52)      61440=(2^(13-1)*3^(2-1)*5^(2-1))
27(54)      6300=(2^(3-1)*3^(3-1)*5^(3-1)*7^(2-1))
28(56)      6720=(2^(7-1)*3^(2-1)*5^(2-1)*7^(2-1))
29(57)      2359296=(2^(19-1)*3^(3-1))
30(60)      5040=(2^(5-1)*3^(3-1)*5^(2-1)*7^(2-1))
31(62)      3221225472=(2^(31-1)*3^(2-1))
32(64)      7560=(2^(4-1)*3^(4-1)*5^(2-1)*7^(2-1))
33(66)      46080=(2^(11-1)*3^(3-1)*5^(2-1))
34(68)      983040=(2^(17-1)*3^(2-1)*5^(2-1))
35(70)      25920=(2^(7-1)*3^(5-1)*5^(2-1))
36(72)      12600=(2^(4-1)*3^(3-1)*5^(3-1)*7^(2-1))
37(74)      206158430208=(2^(37-1)*3^(2-1))
38(75)      32400=(2^(5-1)*3^(5-1)*5^(3-1))
39(78)      184320=(2^(13-1)*3^(3-1)*5^(2-1))
40(80)      15120=(2^(5-1)*3^(4-1)*5^(2-1)*7^(2-1))
41(81)      44100=(2^(3-1)*3^(3-1)*5^(3-1)*7^(3-1))
42(84)      20160=(2^(7-1)*3^(3-1)*5^(2-1)*7^(2-1))
43(85)      5308416=(2^(17-1)*3^(5-1))
44(88)      107520=(2^(11-1)*3^(2-1)*5^(2-1)*7^(2-1))
45(90)      25200=(2^(5-1)*3^(3-1)*5^(3-1)*7^(2-1))
46(91)      2985984=(2^(13-1)*3^(7-1))
47(93)      9663676416=(2^(31-1)*3^(3-1))
48(96)      27720=(2^(4-1)*3^(3-1)*5^(2-1)*7^(2-1)*11^(2-1))
49(98)      233280=(2^(7-1)*3^(7-1)*5^(2-1))
50(100)      45360=(2^(5-1)*3^(5-1)*5^(2-1)*7^(2-1))
0
 

Author Comment

by:Nusrat Nuriyev
ID: 40396568
okay , the main question is about
this:

4(8)      24=(2^(4-1)*3^(2-1))

why not this?
4(8)      X=(2^(2-1)*3^(2-1)*5^(2-1))
?
Even greater example.

8(16)      120=(2^(4-1)*3^(2-1)*5^(2-1))

why not
8(16)      120=(2^(2-1)*3^(4-1)*5^(2-1))

Or generally, the question:
Given a number:
66150
factorization:
2 3 3 3 5 5 7 7

How to generate this from the upper?
6 9 5 5 7 7

How to  generate all combinations?
0
Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
LVL 84

Expert Comment

by:ozo
ID: 40397024
why not this?
4(8)      X=(2^(2-1)*3^(2-1)*5^(2-1))
Because 30 > 24, and you wanted "the least number n"

for 2 3 3 3 5 5 7 7, the  least number seems to be 2^(7-1)*3^(7-1)*5^(5-1)*7^(5-1)*11^(3-1)*13^(3-1)*17^(3-1)*19^(2-1)
0
 

Author Comment

by:Nusrat Nuriyev
ID: 40397200
I know, but how to get ALL that combinations to get the minimum?
how to generate all such combinations?
0
 
LVL 84

Expert Comment

by:ozo
ID: 40397263
At first I thought you only need to try combining the smallest factors, but in the case of 3 3 3 2 2
it turns out that 6 3 3 2 gives a smaller n than 4 3 3 3, so it looks like you have to try all combinations
0
 
LVL 84

Expert Comment

by:ozo
ID: 40397299
So my earlier result can be improved with
36(72)      10080=(2^(6-1)*3^(3-1)*5^(2-1)*7^(2-1))
0
 

Author Comment

by:Nusrat Nuriyev
ID: 40448594
Still not clear how to generate all that combinations.
0
 
LVL 84

Expert Comment

by:ozo
ID: 40448994
#!/usr/bin/perl
use strict;
use warnings;
use POSIX;
use constant PRIME=>qw(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 );
sub factors{
    my $n=shift;
    my @a;
    my $a=0;
    while( $n%2==0 ){ $n/=2; unshift @a,2; }
    my $p=3;
    while( $n>=$p*$p ){
	while( $n%$p == 0 ){ $n/=$p; unshift @a,$p; }
	$p+=2;
    }
    unshift @a,$n if $n!=1;
    return @a;
}

sub cmpp{
    my @p=@{+shift};
    my @q=@{+shift};
    push @p,(1)x($#q-$#p);
    push @q,(1)x($#p-$#q);
    my($p,$q)=(1,1);
    for( 0..$#p ){
	$p*=(PRIME)[$_]**($p[$_]-$q[$_]) if $p[$_]>$q[$_];
	$q*=(PRIME)[$_]**($q[$_]-$p[$_]) if $q[$_]>$p[$_];
    }
    if( $p==$q && $p == 'inf' ){ 
	print  "$p==$q (@p):(@q)\n";
        ($p,$q)=(0,0);
        for( 0..$#p ){
  	  $p+=log((PRIME)[$_])*($p[$_]-$q[$_]) if $p[$_]>$q[$_];
	   $q+=log((PRIME)[$_])*($q[$_]-$p[$_]) if $q[$_]>$p[$_];
        }
	print "exp($p)<=>exp($q)\n";
    }
    #die "$p==$q (@p):(@q)" if $p==$q;
    return $p<=>$q;
}
my %min;
sub minp{
    my @a=@_;
    my %p;
    my ($i,$j,$m);
    for( $i=0; $i<$#_ && 2**$_[$i] >= (PRIME)[$#_]**2; ++$i ){};
    if( my $aa=$min{$i,@_[$i..$#_]} ){
	@a=(@a[0..$i-1],@$aa);
    }else{
	my $i0=$i;
        for( ;$i<$#_; ++$i ){
	  for $j($i+1..$#_ ){
	    if( ($m=$_[$i]*$_[$j]) < 1000 && !$p{$m}++ ){
              my @aa=minp(sort{$b<=>$a}($m,@_[0..$i-1,$i+1..$j-1,$j+1..$#_]));
	      @a=@aa if cmpp(\@a,\@aa) >0;
            }
          }
	}
	$min{$i0,@_[$i0..$#_]}=[@a[$i0..$#a]];
    }
    return @a;
}
sub p{
    my $n=1;
    my $p="";
    for( reverse 0..$#_ ){
	my $m=$n*(PRIME)[$_]**($_[$_]-1);
	if( $m<'inf' ){
	    $n=$m;
	}else{
	    $p=(PRIME)[$_]."^".($_[$_]-1)."*$p";
        }
    }
    return $p.$n;
}

$"="*";
for my $k(1..5000){
    my @f0=minp(factors($k*2));
    my @f1=minp(factors($k*2-1));
    my $K=2*$k;
    ($K,@f0)=($K-1,@f1) if cmpp(\@f0,\@f1)>0;
    my $n0=p(@f0);
    my @f=map{(PRIME)[$_]."^($f0[$_]-1)"}0..$#f0;
    print "$k($K)\t$n0=(@f)\n";
}

Open in new window

0
 

Author Comment

by:Nusrat Nuriyev
ID: 40471611
I don't know perl enough. Could you post in C++?
0
 
LVL 84

Accepted Solution

by:
ozo earned 500 total points
ID: 40473141
// for simplicity, this C++ version omits the Dynamic Programming cache of subproblem results,  so it can get slow for large k
#include <iostream>
#include <set>
#include <map>
#include <math.h>   
using namespace std;
int PRIME[]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251};
multiset<int> factors(int n){
    multiset <int>a;
    while( n%2==0 ){ n/=2; a.insert(2); }
    int p=3;
    while( n>=p*p ){
	while( n%p == 0 ){ n/=p; a.insert(p); }
	p+=2;
    }
    if( n!=1 ){ a.insert(n); }
    return a;
}

int cmpp(multiset<int>p,multiset<int>q){
    while( p.size()<q.size() ){ p.insert(1); }
    while( q.size()<p.size() ){ q.insert(1); }
    double P=1;
    double Q=1;
    multiset<int>::reverse_iterator p_;
    multiset<int>::reverse_iterator q_;
    int _;
    for( _=0,p_=p.rbegin(),q_=q.rbegin(); p_!=p.rend()&&q_!=q.rend(); ++p_,++q_,++_ ){
        if( *p_>*q_ ){ P*=pow(PRIME[_],*p_-*q_); }
        if( *q_>*p_ ){ Q*=pow(PRIME[_],*q_-*p_); }

    }
    if( P== std::numeric_limits<double>::infinity() && Q== std::numeric_limits<double>::infinity() ){
        P=Q=0;
        for( _=0,p_=p.rbegin(),q_=q.rbegin(); p_!=p.rend()&&q_!=q.rend(); ++p_,++q_,++_ ){
            if( *p_>*q_ ){ P+=log(PRIME[_])*(*p_-*q_); }
            if( *q_>*p_ ){ Q+=log(PRIME[_])*(*q_-*p_); }
        }
    }
    return P<Q?-1:P>Q?1:0;
}
//map<mutiset<int>,multiset<int> > min;
multiset<int> minp(multiset<int>A){
    multiset<int>a=A;
    map<int,int>p;
    multiset<int>::reverse_iterator i;
    multiset<int>::reverse_iterator j;
    int m;
    for( i=A.rbegin();
         i!=A.rend() && pow(2,*i) > pow(PRIME[a.size()-1],2);
         ++i
    ){}
    //   
   for( ; i!=A.rend(); ++i ){
	for( j=i;++j!=A.rend(); ){
	    if( (m=*i * *j) < 1000 && !p[m]++ ){
                 multiset<int> t;
                 for( multiset<int>::reverse_iterator k=A.rbegin();k!=A.rend();++k ){
 		       if( k!= i && k!= j ){ t.insert(*k); }
                 }
                 t.insert(m);
                 multiset<int>aa=minp(t);
                 if( cmpp(a,aa) > 0 ){
                      a=aa;
                 }
             }
        }
    }
    //
    return a;
}
void print(multiset<int>P){
    double n=1;
    multiset<int>::reverse_iterator P_;
    int _;
    cout.precision(numeric_limits<double>::digits10);
    for( P_=P.rbegin(),_=0;P_!=P.rend(); ++P_,++_ ){
	double m=n*pow(PRIME[_],*P_-1);
	if( m< numeric_limits<double>::infinity() ){
	    n=m;
        }else{
	    cout << (PRIME)[_] << "^" << (*P_-1) << "*";
        }
    }
    cout << n;
}

int main(){
 for( int k=1; k<5000;++k ){
    multiset<int> f0=minp(factors(k*2));
    multiset<int> f1=minp(factors(k*2-1));
    int K=2*k;
    if( cmpp(f0,f1)>0 ){
       K=K-1;
       f0=f1;
    }
    cout << k << "(" << K << ")\t" ;
    print(f0);
    cout << "=(";
    int _=f0.size();
    for( auto f0_:f0 ){
      cout << PRIME[--_] << "^(" << f0_ << "-1)";
      if( _ > 0 ){ cout << "*"; }
    }
    cout << ")" << endl;
 }
}

Open in new window

0
 

Author Comment

by:Nusrat Nuriyev
ID: 40490121
Compiler says numeric_limits is undefined
Okay, never mind.
0
 
LVL 84

Assisted Solution

by:ozo
ozo earned 500 total points
ID: 40490335
numeric_limits should be part of std:: but maybe you need to include <limits>
Or you don't even really need to use numeric_limits, since <double>::digits10 only lets you see more digits of the result.
You can put any number there, and the full factorization is displayed anyway, so you still get a precise answer even when you don't cout all the digits.
And any number would also work in place of <double>::infinity.
In cmpp, it is used to fall back to a log compare when a direct comparison overflows, but even if you always do a log compare it should be sufficiently accurate and not horribly slow.
And in print it is just used to decide when you can only display factors because the value is too big to display directly,
but you may even prefer a factorized display before the value overflows a double.
0

Featured Post

Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Iteration: Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every mont…
When there is a disconnect between the intentions of their creator and the recipient, when algorithms go awry, they can have disastrous consequences.
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
In this video, viewers are given an introduction to using the Windows 10 Snipping Tool, how to quickly locate it when it's needed and also how make it always available with a single click of a mouse button, by pinning it to the Desktop Task Bar. Int…

717 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question