Task on number theory

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.
Nusrat NuriyevAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

ozoCommented:
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
ozoCommented:
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
Nusrat NuriyevAuthor Commented:
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
Cloud Class® Course: SQL Server Core 2016

This course will introduce you to SQL Server Core 2016, as well as teach you about SSMS, data tools, installation, server configuration, using Management Studio, and writing and executing queries.

ozoCommented:
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
Nusrat NuriyevAuthor Commented:
I know, but how to get ALL that combinations to get the minimum?
how to generate all such combinations?
0
ozoCommented:
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
ozoCommented:
So my earlier result can be improved with
36(72)      10080=(2^(6-1)*3^(3-1)*5^(2-1)*7^(2-1))
0
Nusrat NuriyevAuthor Commented:
Still not clear how to generate all that combinations.
0
ozoCommented:
#!/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
Nusrat NuriyevAuthor Commented:
I don't know perl enough. Could you post in C++?
0
ozoCommented:
// 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

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Nusrat NuriyevAuthor Commented:
Compiler says numeric_limits is undefined
Okay, never mind.
0
ozoCommented:
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
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Algorithms

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.