Project Euler Problem 276, 268, 347

newkid

那个BOZO排序的，把4!各种平均次数设为未知数，列出所有排列得到24元一次方程组。
可以拿简化的三张牌每次交换两张来试验。

〇〇

368的前半部分证明
Solution to puzzle 72: Depleted harmonic seriesfile:///C:/Downloads/s.gifIt is well known that the harmonic series, 1/1 + 1/2 + 1/3 + 1/4 + ... , diverges.  Consider a depleted harmonic series; see below; which contains only terms whose denominator does not contain a 9.  (In decimal representation.)  Does this series diverge or converge?
S = 1/1 + 1/2 + ... + 1/8 + 1/10 + ... + 1/18 + 1/20 + ... + 1/88 + 1/100 + 1/101 + ...

---

Grouping terms according to the number of digits in their denominator, we have

Sn = (1/1 + ... + 1/8) + (1/10 + ... + 1/18 + 1/20 + ... + 1/88) + (1/100 + ... + 1/888) + ... + (1/10n−1 + ... + 1/8...8 [n eights])

Now form another series, which is term-for-term greater than or equal to Sn, by setting each term with k digits in the denominator to 1/10k−1:

Tn = (1/1 + ... + 1/1) + (1/10 + ... + 1/10) + (1/100 + ... + 1/100) + ... + (1/10n−1 + ... + 1/10n−1)

Note that the number of k-digit numbers without a 9 is 8×9k−1.
(There are 8 choices for the leading digit, and 9 choices for each of the other digits.)
Hence

Tn = 8×1 + (8×9)/10 + (8×92)/102 + ... + (8×9n−1)/10n−1

This is a geometric series with first term 8, common ratio 9/10, and n terms.
Therefore Tn = 80[1 − (9/10)n]
As n file:///C:/Downloads/ttinf.gif, Tn file:///C:/Downloads/tt.gif 80.
That is, the infinite series, T, converges to 80; T = T∞ = 80.
By the Comparison Test, and since at least one term in Sn is strictly less than the corresponding term in Tn, the infinite series,

S = (1/1 + ... + 1/8) + (1/10 + ... + 1/18 + 1/20 + ... + 1/88) + (1/100 + ... + 1/888) + ... < 80.

That is, S converges, to a value less than 80.

---

RemarksSpot the flaw in the following two 'proofs' that the harmonic series converges!
Proof by SumLet Sn denote the sum of those terms of the harmonic series whose denominators do not contain the decimal digit n.
We have already seen that S9 < 80.  It can similarly be shown that Sn < 80, for 1 ≤ n ≤ 8, and that S0 < 90.
Since each Sn is absolutely convergent, S0 + S1 + ... + S9 < 810.
Since each term in the harmonic series occurs in at least one series, Sn, it follows that the harmonic series itself converges.
Proof by ComparisonConsider S9, and its complementary series, T9, in which each term contains at least one 9:

S9 = 1/1 + 1/2 + ... + 1/8 + 1/10 + ... + 1/18 + 1/20 + ...

T9 = 1/9 + 1/19 + ... + 1/89 + 1/90 + ... + 1/99 + 1/109 + ...

Since T9 is less, term-for-term, than S9, which converges, it follows from the Comparison Test that T9 also converges.
Moreover, both S9 and T9 are absolutely convergent; hence their sum, the harmonic series, converges.
The Kempner-depleted harmonic sumsDepleted harmonic series were first studied by A. J. Kempner in 1914.  Consider Sn, as defined above.  R. Baillie has provided a method for summing the series with great accuracy and economy, given to five decimal places in the table below.  (Source: Section 3.3 of Gamma: Exploring Euler's Constant, by Julian Havil.)
Kempner-depleted harmonic sumsMissing digitSum
116.17696
219.25735
320.56987
421.32746
521.83460
622.20559
722.49347
822.72636
922.92067
023.10344

---

Further reading

• Kempner Series
• The Harmonic Numbers and Series
• In perfect harmony
• Rearranging the Alternating Harmonic Series
• file:///C:/Downloads/pdf.gif Random Harmonic Series
  

Source: A. J. Kempner

〇〇

368
lim(sum(1/n)-ln(n))是欧拉常数
    0.5772156649
n=1000000000可以精确到小数点后第8位
    0.5772156654
用它来计算
因为已知no9的KEMPNER序列收敛，那么必定有一个极限k
=lim(sum(1/n ,n no9))
与此相对应，带9的序列必发散，它与ln(n)的差应该也是常数
只要计算这个大约的常数就可以推导出k
但是对更稀疏的序列求和需要计算更多个数才能达到精度，目前还是不可行的
没有9和没有3个连续相同数字的比例
select l,s,s2,s9,s2/s from(
select length(l)l,sum(1)s,sum(decode(instr(l,9),0,1))s9,sum(case when instr(l,'111')+instr(l,'222')+instr(l,'333')
+instr(l,'444')+instr(l,'555')+instr(l,'666')+instr(l,'777')+instr(l,'888')+instr(l,'999')
+instr(l,'000')=0
then 1 end)s2
from(select level l from dual connect by level<=:x) group by length(l)
);
         L          S         S2         S9       S2/S
---------- ---------- ---------- ---------- ----------
         1          9          9          8          1
         2         90         90         72          1
         3        900        891        648        .99
         4       9000       8829       5832       .981
         5      90000      87480      52488       .972
         6     900000     866781     472392     .96309
         7          1                     1

〇〇

Problem 369
29 January 2012


In a standard 52 card deck of playing cards, a set of 4 cards is a Badugi if it contains 4 cards with no pairs and no two cards of the same suit.

Let f(n) be the number of ways to choose n cards with a 4 card subset that is a Badugi. For example, there are 2598960 ways to choose five cards from a standard 52 card deck, of which 514800 contain a 4 card subset that is a Badugi, so f(5) = 514800.

Find∑ f(n) for 4 ≤ n ≤ 13.

〇〇

〇〇 发表于 2012-1-29 12:12
Problem 369
29 January 2012

用插入排序算出了5张牌，4张牌就是t1的行数17160
col a for a10
with t as(select level l from dual connect by level<=13)--数字
,t1 as(select chr(a.l+64)a,chr(b.l+64+13)b,chr(c.l+64+26)c,chr(d.l+64+39)d --所有不同花色和数字
from t a,t b,t c,t d
where a.l not in(b.l,c.l,d.l)
and b.l not in(a.l,c.l,d.l)
and c.l not in(a.l,b.l,d.l)
and d.l not in(a.l,c.l,b.l)
)
select count(distinct s)*4 --每种花色都是对称的，只要算一种
from(select case when a<x then a||x else x||a end||b||c||d s from t1,
(select chr(64+l)x from t)--第5张牌
where a<>x)
;
COUNT(DISTINCTS)*4--每种花色都是对称的，只要算一种
--------------------------------------------------
                                            514800

已用时间:  00: 00: 01.00

〇〇

6张牌还能分析一下，更多的就数不清了
情况1：最后2张同花色，那么=第一、一种花色牌*4
情况2：最后2张不同花色，，那么=第一、二种花色牌*6

〇〇

Problem 370
05 February 2012


Let us define a geometric triangle as an integer sided triangle with sides a ≤ b ≤ c so that its sides form a geometric progression, i.e. b^2 = a · c .

An example of such a geometric triangle is the triangle with sides a = 144, b = 156 and c = 169.

There are 861805 geometric triangles with perimeter  ≤ 10^6 .

How many geometric triangles exist with perimeter  ≤ 2.5·10^13 ?

〇〇

〇〇 发表于 2012-2-6 12:33
Problem 370
05 February 2012

a=1,b=sqrt(c)显然是不行的1 2 4不能组成三角形。。
a=b=c显然一定行

〇〇

〇〇 发表于 2012-2-6 12:33
Problem 370
05 February 2012

边长10000以内已经很慢了,c程序马上出结果
SQL> var x number
SQL> exec :x:=10000

PL/SQL procedure successfully completed.

Elapsed: 00:00:00.01
SQL> with t as(select level a from dual connect by level <=:x)
  2  ,t2 as(select level c from dual connect by level <=:x)
  3  select /*a,sqrt(a*c),c*/count(*) from t,t2 where a>1 and a<c and sqrt(a*c)=trunc(sqrt(a*c))and
  4  a+sqrt(a*c)>c and a<=sqrt(a*c) and sqrt(a*c)<=c and
  5  a+sqrt(a*c)+c<=1e6;

  COUNT(*)
----------
      8341

Elapsed: 00:01:52.36

〇〇

〇〇 发表于 2012-2-6 14:06
a=1,b=sqrt(c)显然是不行的1 2 4不能组成三角形。。
a=b=c显然一定行

从前几个结果看出：要么a c都是完全平方数，要么都是完全平方数的同样的倍数

         A  SQRT(A*C)          C
---------- ---------- ----------
         4          6          9
         8         12         18
         9         12         16
        12         18         27
        16         20         25
        16         24         36
        18         24         32
        20         30         45
        24         36         54
        25         30         36