Six-brilliant numbers

[fivemack]

That is, numbers with six prime factors all of the same number of digits. Ones marked with dots are by-definition otherwise by search; there are obviously no 7-digit without dupes.

.1771561	11,11,11,11,11,11	smallest 7-digit with dupes
9887999		11,11,11,17,19,23	largest 7-digit with dupes
10081357	11,11,13,13,17,29	smallest 8-digit with dupes
.30808063	11,13,17,19,23,29	smallest 8-digit without dupes
99423181	11,13,19,23,37,43	largest 8-digit without dupes
99990407	11,11,19,23,31,61	largest 8-digit with dupes
100016059	11,11,13,13,67,73	smallest 9-digit with dupes
100145903	11,13,19,29,31,41	smallest 9-digit without dupes
999978551	11,13,29,51,61,67	largest 9-digit with or without dupes
1000052443	13,23,29,29,41,97	smallest 10-digit with dupes
1000202489	11,13,29,43,71,79	smallest 10-digit without dupes
9999884737	19,31,43,67,71,83	largest 10-digit with or without dupes
10000108889	23,29,59,59,59,73	smallest 11-digit with dupes
10000268641	11,31,43,79,89,97	smallest 11-digit without dupes
99919838357	53,61,67,71,73,89	largest 11-digit without dupes
99998113069	47,61,61,83,83,83	largest 11-digit with dupes
100000197487	41,53,67,73,97,97	smallest 12-digit with dupes
100042414319	53,59,61,71,83,89	smallest 12-digit without dupes
.293391909323	71,73,79,83,89,97	largest 12-digit without dupes
.832972004929	97,97,97,97,97,97	largest 12-digit with dupes

For 13..18 I think this is a relatively easy sort-and-search, for 19..24 it's quite a large one, for larger numbers it starts to become interesting

[fivemack]

1061520150601		101 101 101 101 101 101	with (!)
1741209542339		101 103 107 109 113 127	without (!)
9999901067561		101 107 109 139 157 389	without
9999965520509		101 107 113 197 197 211	with

10000001342381		101 101 149 163 181 223	with
10000087934327		101 109 131 149 173 269	without
99999998106163		103 149 179 223 239 683	without
99999999253139		113 181 199 199 331 373	with

100000001274419		101 101 151 211 313 983	with
100000002228881		107 109 113 307 439 563	without
999999998566003		131 167 191 379 653 967	with/without

1000000000407943	151 311 317 379 421 421	with
1000000002307693	109 163 191 593 653 761	without
9999999998178521	131 353 467 647 751 953	with/without

10000000002328283	151 397 467 599 691 863	with/without
99999999886001279	359 631 673 821 877 911	with/without

100000000103742353	563 577 673 751 751 811	with
100000000374707123	401 449 761 773 947 997	without
890969009638765049	967 971 977 983 991 997	without(!)
982134461213542729	997 997 997 997 997 997	with (!)

#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>

using std::vector;
using std::sort;
using std::cout;
using std::endl;

bool isprime(int T)
{
  if (T==2 || T==3) return true;
  if (T%2==0) return false;
  if (T%3==0) return false;
  int s=5,ds=2;
  while (s*s<=T)
    {
      if (T%s==0) return false;
      s+=ds; ds=6-ds;
    }
  return true;
}

int main(void)
{
  vector<double> logthreep;
  vector<int> primes;
  for (int i=100; i<1000; i++)
    if(isprime(i))
      primes.push_back(i);
  int pn = primes.size();
  for (int pi1=0; pi1<pn; pi1++)
  for (int pi2=pi1; pi2<pn; pi2++)
  for (int pi3=pi2; pi3<pn; pi3++)
    {
      logthreep.push_back(log(primes[pi1])+log(primes[pi2])+log(primes[pi3]));
    }
  cout << logthreep.size() << "\n\n";
  sort(logthreep.begin(), logthreep.end());
  double target = 14.0*log(10);
  double XXH,XXH1,XXH2,XXL,XXL1,XXL2;
  XXH=XXH1=XXH2=1e9;
  XXL=XXL1=XXL2=-1e9;
  for (int q=0; q<logthreep.size(); q++)
    {
      double t2 = target-logthreep[q];
      vector<double>::iterator ilo,ihi;
      ihi = lower_bound(logthreep.begin(), logthreep.end(), t2);
      if (ihi != logthreep.begin())
	{
	  ilo = ihi-1;
	  if (*ilo!=0)
	    {
	      if (logthreep[q]+*ilo > XXL) { XXL1=logthreep[q]; XXL2=*ilo; XXL=XXL1+XXL2; }
	      if (logthreep[q]+*ihi < XXH) { XXH1=logthreep[q]; XXH2=*ihi; XXH=XXH1+XXH2; }
	      long long U0 = (int)(0.1+exp(logthreep[q]));
	      long long U1 = (int)(0.1+exp(*ilo));
	      long long U2 = (int)(0.1+exp(*ihi));
	      cout << q << " " << U0 << " " << U1 << " " << U2 << " " << U0*U1 << " " << U0*U2 << endl;
	      cout << q << " " << (int)(0.1+exp(*ilo)) << " " << (int)(0.1+exp(*ihi)) << endl;
	    }
	}
    }
  printf("%30.28f %30.28f\n%30.28f %30.28f\n",exp(XXL1),exp(XXL2),exp(XXH1),exp(XXH2));
}

Behaviour isn't quite right for the larger values of target, so I had to wrap it in something like

./meeble |awk 'NF==6 && $4!=1' | sort -gk6|awk '{print $6}' | uniq -c | head

[science_man_88]

I'm guessing:

isbrilliant(x,y)=for(z=2^x,10^y,if(sum(a=1,if(#factor(z)[,2]<6,#factor(z)[,2],break()),factor(z)[a,2])==6,print(z)))

is more of what you wanted ?

[fivemack]

Originally Posted by science_man_88

I'm guessing:

isbrilliant(x,y)=for(z=2^x,10^y,if(sum(a=1,if(#factor(z)[,2]<6,#factor(z)[,2],break()),factor(z)[a,2])==6,print(z)))

is more of what you wanted ?

Yes; though I found that computing a GCD with the product of the usable primes (raised to the sixth power if you want to allow duplicates) was rather quicker than doing a full factorisation every time; this is obviously a sievable problem but I haven't implemented the sieve yet.

The C++ sort-and-search code I posted gives the wrong answer for the 22-digit case, because 53-bit doubles aren't wide enough, though obviously the answer from the C++ code bounds the size of the area you'd have to sieve.

[science_man_88]

Originally Posted by fivemack

Yes; though I found that computing a GCD with the product of the usable primes (raised to the sixth power if you want to allow duplicates) was rather quicker than doing a full factorisation every time; this is obviously a sievable problem but I haven't implemented the sieve yet.

The C++ sort-and-search code I posted gives the wrong answer for the 22-digit case, because 53-bit doubles aren't wide enough, though obviously the answer from the C++ code bounds the size of the area you'd have to sieve.

I'm a little lost as to why that would be quicker unless maybe useable primes is not 2-sqrt(number to check) because GCD(sqrt(number to check)#,number to check) == number to check.

[Dubslow]

Originally Posted by science_man_88

I'm a little lost as to why that would be quicker unless maybe useable primes is not 2-sqrt(number to check) because GCD(sqrt(number to check)#,number to check) == number to check.

What he's saying is that if you're looking for (e.g.) 3-digit six-brilliant numbers, then you don't need to check a number for 2 digit, 4 digit, 5 digit, etc... factors; you only need to check for 3 digit factors which can be done (in this example) with and seeing what you get. (To check for duplicates you'd need to put a power of six/whatever on each prime.)




(Excuse the poor tex, it may or may not be better than "GCD(1000#/100#, n)". )

[science_man_88]

Originally Posted by Dubslow

What he's saying is that if you're looking for (e.g.) 3-digit six-brilliant numbers, then you don't need to check a number for 2 digit, 4 digit, 5 digit, etc... factors; you only need to check for 3 digit factors which can be done (in this example) with and seeing what you get. (To check for duplicates you'd need to put a power of six/whatever on each prime.)




(Excuse the poor tex, it may or may not be better than "GCD(1000#/100#, n)". )

if you look for only 3 digit factors of a 3 digit number then you don't catch 3^6=729 you also miss any under 300 since 300/3=100 the lowest 3 digit divisor you can start with ( technically it starts at 303 that you could check).

okay never mind it's >202 that it tells you anything because it's the first multiple of a prime with 3 or more digits.

[Dubslow]

Originally Posted by science_man_88

if you look for only 3 digit factors of a 3 digit number then you don't catch 3^6=729 you also miss any under 300 since 300/3=100 the lowest 3 digit divisor you can start with ( technically it starts at 303 that you could check).

???????
"numbers with six prime factors all of the same number of digits"

729 isn't prime; 3 is certainly not a 3 digit prime. And last time I checked, no 3 digit number will have 6 3-digit prime factors. Also last time I checked, if you do GCD(101, a number with 101 in its factorization), you'll get at least 101. I fail to see what 300 has to do with that.

[science_man_88]

Originally Posted by Dubslow

???????
"numbers with six prime factors all of the same number of digits"

729 isn't prime; 3 is certainly not a 3 digit prime. And last time I checked, no 3 digit number will have 6 3-digit prime factors. Also last time I checked, if you do GCD(101, a number with 101 in its factorization), you'll get at least 101. I fail to see what 300 has to do with that.

3 has the same number of digits as 3 , 3 to the power of 6 is 729 is a number, therefore 729 is 6 brilliant

(22:31)>isbrilliant(6,3,4)
144
160
216
224
240
324
336
352
360
400
416
486
504
528
540
544
560
600
608
624
729
736
756
784
792
810
816
840
880
900
912
928
936
992
1000

and yes I messed up with the 300, but I did do a code that does:

for(n=100,999,print(gcd(prod(X=26,68,prime(X))^6,n)","n))

and the first time it doesn't give 1 or the number is 202. okay I'll admit it I got lost I messed 168 to 68 but I retested and 202 still stands at the minimum. the minimum 3 digit 6-brilliant is 3^2*2^4 = 144

[Dubslow]

Originally Posted by science_man_88

<snip>

Whoops, I made a typo. Where I said "3-digit 6-brilliant numbers" I was thinking in my head "6-brilliant numbers whose factors have 3 digits". That's what I was writing about.

[CRGreathouse]

Originally Posted by Dubslow

Whoops, I made a typo. Where I said "3-digit 6-brilliant numbers" I was thinking in my head "6-brilliant numbers whose factors have 3 digits". That's what I was writing about.

Right, that's kind of the natural way of thinking about them.

The counts of such numbers are not in the OEIS, but the counts for the analogous semiprimes are A087434. The formula is straightforward and gives

84, 230230, 13172431272, 2009505083440218, 476013062485109252824, 148697710093074782891561317, 56289121765869792295257792982777, 24349676137284030200879331533337194376, 11666012947107695154385353794415395985137344, 6057277355183085204144847469602671151899349499197, 3354985557158369214407984988027190131369315871722691152, 1959509071991741722270413421131623309713272464704021335869310, 1196301271416935612331559019142578123179924493160149725594041285390, 758297477798207294085616092160894284729546088426880198004979229145638184, 496405409134346365011354234191682214886538111380694256570445787621168130062528, 334180505840507943479437772268647724355589483819448761562142733090916595143509225212, 230551283386125977830557515195210002315457614489571967352960948012129577632233414552542796, 162537577146540321845227986334505185151917953317422163374965016524615696383252603524891046763532, 116816284673708680421835123424581599081284210871219523674771358297205544299884690188130918699786791500, 85416640764723824021108446456250433057219850414437417656346074325343176420847706796002701169332531133021551, 63434778901223585384265131927059356802305353342435316304189778022372093879998625701188622017546319272210868240784, 47777139494090360016305651100722437896951187322404498059597560979956679547504643361209098188623110927359491777939720841, 36447608389806648140714977201273896196346361099368631002618281535486043280009949162450062261360663543889016612413795952580291, 28131574280009154082710448682314774375712261908758572574980667541365874655616083694412009836355371649813984129660663498677543353152, ...

six-brilliant numbers composed of 1, 2, ... digit prime factors.