欧拉计划757：隐身数

〇〇

〇〇 发表于 2021-6-4 08:43
python 算到10**9就很慢了def f(x): s=set() for a in range(1,int(x**0.5*1.5)):  for c in range(a+1,a+a ...

刚才把c的上限改错了，重新
改成这样
def f(x):
s=set()
u=int(x**0.5)+1
for a in range(1,u):
  for c in range(a+1,a+a if a+a<u else u):
   if a*c %(c-a)==0:
     n=a*c*(c-a+1)/(c-a)
     if n%a==0 and n%c==0 and n<=x:
       s.add(n)
return len(s)+1

for n in range(6,9):
t=time.time();print(f(10**n),time.time()-t)

...
2851 0.05999994277954**6
10908 0.3600003719329834
40517 3.4990084171295166

〇〇

a c其中有一个是质数的n=2ac必是

sqlite> with t as (SELECT value a FROM generate_series(1,1500,1)),
   ...> a as (select a from t),
   ...> c as (select a c from t),
   ...> r as(
   ...> select a*c*(c-a+1)/(c-a) n, a,c from a,c where a<=c and c<a+a and a*c %(c-a)=0)
   ...> select n,a,c, c/a, 2*a*c from r where n<=1000000 and n%a=0 and n%c=0 limit 40;
12|2|3|1|12
24|3|4|1|24
40|4|5|1|40
36|4|6|1|48
60|5|6|1|60
84|6|7|1|84
72|6|8|1|96
72|6|9|1|108
112|7|8|1|112
144|8|9|1|144
120|8|10|1|160
120|8|12|1|192
180|9|10|1|180
144|9|12|1|216
220|10|11|1|220
180|10|12|1|240
180|10|15|1|300
264|11|12|1|264
312|12|13|1|312
252|12|14|1|336
240|12|15|1|360
240|12|16|1|384
252|12|18|1|432
364|13|14|1|364
420|14|15|1|420
336|14|16|1|448
336|14|21|1|588
480|15|16|1|480
360|15|18|1|540
360|15|20|1|600
544|16|17|1|544
432|16|18|1|576
400|16|20|1|640
432|16|24|1|768
612|17|18|1|612
684|18|19|1|684
540|18|20|1|720
504|18|21|1|756
504|18|24|1|864
540|18|27|1|972

〇〇

〇〇 发表于 2021-6-4 10:21
a c其中有一个是质数的n=2ac必是sqlite> with t as (SELECT value a FROM generate_series(1,1500,1)),   . ...

ac只要互质，2ac就是
并且n的因数，最终有两个相邻的数
比如
400=4*5*4*5

540=9*10*2*3

jihuyao

It should be easier to put all factors in different portions and pull out each combination of these partitions one by one to filter out the valid numbers in range such as for N in (0,9), (10, 19), etc.  Since the valid numbers are so sparse it would be interesting to study if certain combinations of the number partitions can be skipped.  Anyway partition plus parallel/distributed calculation is good way to go for brutal force loop calculations.

jihuyao

Let us dig some number fundamentals here.  Consider 6 groups of numbers, 6k+1,6k+2,6k+3,6K+4,6k+5,6k+6.  Apparently there exist no valid requested numbers in two groups 6k+1 and 6k+5 (6k-1).  Because for any 6k-1, it can only be possible 6k-1=(6ki+/-1)*(6j-/+1).  So add any two factors gives a value of 6m.  If both a+b and c+d belong group of 6k and c+d+1 belongs group of 6k+1 then it is impossible to find valid requested numbers for any tested number of N in group of 6k-1.  Similarly one can’t find any valid requested numbers in group of 6k+1.  This cuts 1/3 of the loop.  Did I make any mistake so far with elementary math?  For other groups, given given all possible factoring in (2**x)(3**y)(6mi+1)...(6ni-1)... can we excludes any more groups or sub-group combinations for looping?

jihuyao

Let’s learn elementary math again, any even numbers can have both even and odd factors.  But any odd numbers can only have odd factors.  This means it is impossible to find valid requested numbers in group of odd numbers 2k+1.  This cuts 1/2 of looping.  Now can we find a formula for any even number in form of 2**m(2k+1) to determine if it is a valid requested number???

jihuyao

Did not pay attention to all previous posts.  N=ca(c-a+1)/(c-a) is the needed general formula for verification.  Still feel puzzled why it is so parse.  4 is the first one with 1*4=2*2 and 1+4=2+2+1.  How many can we find on either of two boundaries?  One with a=1 and b=N and c=m and d=N/m, and the other is a=m and b=N/m and c=N**0.5 and d=N**0.5.  Maybe we can find some hints on distribution or density for each range between N**2 and (N+1)**2.

jihuyao

It is much easier to focus on boundaries.  In fact it is easy to prove 4 is the only one for boundary factors (1*4).  And there are only 30 on the other boundary factors (n*n) given N=n*n<=10**6.  To put N=n*n=m*(N/m) and a**2=m, then n=a*(a+1).  When n<=10**3 a(max)=31.  30 is the answer after excluding N=4.  This means, given all even numbers (<=10**6), there many valid ones are determined by middle factors (2<=m<=N**0.5).  There are a few points are interesting.  One is, given N=2k and k is prime.  The other is expanded a little bit, N=2k and k=6i+j and 0<=j<=5.  There can be evenly distributed under given factors???  Further interesting point is the difference of two factors can be any values larger than 0 (1, 2, 3, ...).  What about the distributions over these factor differences???  There can be evenly???   I hope this provides enough medicine for good sleep in following months. LOL

jihuyao

Let us continue the journey.  Clearly, given N=2K and K is prime, no valid one except K=2.  Now consider K=6m+/-1 which are not prime, one can also prove that no valid one can be found.  So I am wondering if it is true for any odd K (K=2i+1) before wasting some pieces of papers.  Now I feel that maybe we can figure out the total count without trial loop.  What is critical is eliminating all the duplicate count using the general formula.  May I say some N can only be duplicated from the general formula calculation (so far I have not run the program at all to list and analyze all the valid ones.  So it seems true there is reason why it is so sparse.

jihuyao

It proves N must even, that is N=2K.  One can also easily proves K must be even too, that is N=4k.  Now from the general formula, N=ac*(c-a+1)/(c-a) and N/a (or N/c) must be integer, c must have c-a as its factor, that is, c=i*(c-a) where i>=1.  Put m=c-a and take a few simple steps, one finds the more meaningful formula, N=i*(i+1)*m*(m+1).  Here i is integer larger than 1 and m=c-a.  Keep in mind, N=c*d and c<=d and a>=1, so m(max)<=N**(0.5)-1.  Based on this formula,  it is easy to see the minimum requirement mentioned before, that is, N=(2**x)(2y+1) where x>=2 and 2y+1 is not prime.  To calculate the total valid N under 10**6, loop m from 1 to m(max) and for each m loop i from 1 to current m (to avoid duplicate N).  The only thing left is if there exists any duplicate in such nested loop calculation (after excluding i/m exchange effect).  Now it may be worth to a program based on the new formula and check wether or not duplicate still exists, and why if not.  I am not sure now if it is possible to get the total valid count without running the program.  But at least it becomes simpler and quicker using the new formula.