Solved

Posted on 2014-10-21
124 Views
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
Question by:Nusrat Nuriyev
• 8
• 5

LVL 84

Expert Comment

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

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

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

LVL 84

Expert Comment

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

I know, but how to get ALL that combinations to get the minimum?
how to generate all such combinations?
0

LVL 84

Expert Comment

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

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

Still not clear how to generate all that combinations.
0

LVL 84

Expert Comment

#!/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";
}
0

Author Comment

I don't know perl enough. Could you post in C++?
0

LVL 84

Accepted Solution

ozo earned 500 total points
// 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;
}
}
0

Author Comment

Compiler says numeric_limits is undefined
Okay, never mind.
0

LVL 84

Assisted Solution

ozo earned 500 total points
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

This algorithm (in C#) will resize any image down to a given size while maintaining the original aspect ratio. The maximum width and max height are both optional but if neither are given, the original image is returned. This example is designed t…
Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your U…
Excel styles will make formatting consistent and let you apply and change formatting faster. In this tutorial, you'll learn how to use Excel's built-in styles, how to modify styles, and how to create your own. You'll also learn how to use your custo…
When you create an app prototype with Adobe XD, you can insert system screens -- sharing or Control Center, for example -- with just a few clicks. This video shows you how. You can take the full course on Experts Exchange at http://bit.ly/XDcourse.