MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  prmreclem5 Structured version   Unicode version

Theorem prmreclem5 13293
Description: Lemma for prmrec 13295. Here we show the inequality  N  / 
2  <  # M by decomposing the set  ( 1 ... N
) into the disjoint union of the set  M of those numbers that are not divisible by any "large" primes (above  K) and the indexed union over  K  <  k of the numbers  W `  k that divide the prime  k. By prmreclem4 13292 the second of these has size less than  N times the prime reciprocal series, which is less than  1  /  2 by assumption, we find that the complementary part  M must be at least  N  /  2 large. (Contributed by Mario Carneiro, 6-Aug-2014.)
Hypotheses
Ref Expression
prmrec.1  |-  F  =  ( n  e.  NN  |->  if ( n  e.  Prime ,  ( 1  /  n
) ,  0 ) )
prmrec.2  |-  ( ph  ->  K  e.  NN )
prmrec.3  |-  ( ph  ->  N  e.  NN )
prmrec.4  |-  M  =  { n  e.  ( 1 ... N )  |  A. p  e.  ( Prime  \  (
1 ... K ) )  -.  p  ||  n }
prmrec.5  |-  ( ph  ->  seq  1 (  +  ,  F )  e. 
dom 
~~>  )
prmrec.6  |-  ( ph  -> 
sum_ k  e.  (
ZZ>= `  ( K  + 
1 ) ) if ( k  e.  Prime ,  ( 1  /  k
) ,  0 )  <  ( 1  / 
2 ) )
prmrec.7  |-  W  =  ( p  e.  NN  |->  { n  e.  (
1 ... N )  |  ( p  e.  Prime  /\  p  ||  n ) } )
Assertion
Ref Expression
prmreclem5  |-  ( ph  ->  ( N  /  2
)  <  ( (
2 ^ K )  x.  ( sqr `  N
) ) )
Distinct variable groups:    k, n, p, F    k, K, n, p    k, M, n, p    ph, k, n, p   
k, W    k, N, n, p
Allowed substitution hints:    W( n, p)

Proof of Theorem prmreclem5
Dummy variables  r  x  q are mutually distinct and distinct from all other variables.
StepHypRef Expression
1 prmrec.3 . . . 4  |-  ( ph  ->  N  e.  NN )
21nnred 10020 . . 3  |-  ( ph  ->  N  e.  RR )
32rehalfcld 10219 . 2  |-  ( ph  ->  ( N  /  2
)  e.  RR )
4 fzfi 11316 . . . . . 6  |-  ( 1 ... N )  e. 
Fin
5 prmrec.4 . . . . . . 7  |-  M  =  { n  e.  ( 1 ... N )  |  A. p  e.  ( Prime  \  (
1 ... K ) )  -.  p  ||  n }
6 ssrab2 3430 . . . . . . 7  |-  { n  e.  ( 1 ... N
)  |  A. p  e.  ( Prime  \  (
1 ... K ) )  -.  p  ||  n }  C_  ( 1 ... N )
75, 6eqsstri 3380 . . . . . 6  |-  M  C_  ( 1 ... N
)
8 ssfi 7332 . . . . . 6  |-  ( ( ( 1 ... N
)  e.  Fin  /\  M  C_  ( 1 ... N ) )  ->  M  e.  Fin )
94, 7, 8mp2an 655 . . . . 5  |-  M  e. 
Fin
10 hashcl 11644 . . . . 5  |-  ( M  e.  Fin  ->  ( # `
 M )  e. 
NN0 )
119, 10ax-mp 5 . . . 4  |-  ( # `  M )  e.  NN0
1211nn0rei 10237 . . 3  |-  ( # `  M )  e.  RR
1312a1i 11 . 2  |-  ( ph  ->  ( # `  M
)  e.  RR )
14 2nn 10138 . . . . 5  |-  2  e.  NN
15 prmrec.2 . . . . . 6  |-  ( ph  ->  K  e.  NN )
1615nnnn0d 10279 . . . . 5  |-  ( ph  ->  K  e.  NN0 )
17 nnexpcl 11399 . . . . 5  |-  ( ( 2  e.  NN  /\  K  e.  NN0 )  -> 
( 2 ^ K
)  e.  NN )
1814, 16, 17sylancr 646 . . . 4  |-  ( ph  ->  ( 2 ^ K
)  e.  NN )
1918nnred 10020 . . 3  |-  ( ph  ->  ( 2 ^ K
)  e.  RR )
201nnrpd 10652 . . . . 5  |-  ( ph  ->  N  e.  RR+ )
2120rpsqrcld 12219 . . . 4  |-  ( ph  ->  ( sqr `  N
)  e.  RR+ )
2221rpred 10653 . . 3  |-  ( ph  ->  ( sqr `  N
)  e.  RR )
2319, 22remulcld 9121 . 2  |-  ( ph  ->  ( ( 2 ^ K )  x.  ( sqr `  N ) )  e.  RR )
242recnd 9119 . . . . . 6  |-  ( ph  ->  N  e.  CC )
25242halvesd 10218 . . . . 5  |-  ( ph  ->  ( ( N  / 
2 )  +  ( N  /  2 ) )  =  N )
267a1i 11 . . . . . . . . 9  |-  ( ph  ->  M  C_  ( 1 ... N ) )
2715peano2nnd 10022 . . . . . . . . . . . . 13  |-  ( ph  ->  ( K  +  1 )  e.  NN )
28 elfzuz 11060 . . . . . . . . . . . . 13  |-  ( k  e.  ( ( K  +  1 ) ... N )  ->  k  e.  ( ZZ>= `  ( K  +  1 ) ) )
29 nnuz 10526 . . . . . . . . . . . . . 14  |-  NN  =  ( ZZ>= `  1 )
3029uztrn2 10508 . . . . . . . . . . . . 13  |-  ( ( ( K  +  1 )  e.  NN  /\  k  e.  ( ZZ>= `  ( K  +  1
) ) )  -> 
k  e.  NN )
3127, 28, 30syl2an 465 . . . . . . . . . . . 12  |-  ( (
ph  /\  k  e.  ( ( K  + 
1 ) ... N
) )  ->  k  e.  NN )
32 eleq1 2498 . . . . . . . . . . . . . . . . 17  |-  ( p  =  k  ->  (
p  e.  Prime  <->  k  e.  Prime ) )
33 breq1 4218 . . . . . . . . . . . . . . . . 17  |-  ( p  =  k  ->  (
p  ||  n  <->  k  ||  n ) )
3432, 33anbi12d 693 . . . . . . . . . . . . . . . 16  |-  ( p  =  k  ->  (
( p  e.  Prime  /\  p  ||  n )  <-> 
( k  e.  Prime  /\  k  ||  n ) ) )
3534rabbidv 2950 . . . . . . . . . . . . . . 15  |-  ( p  =  k  ->  { n  e.  ( 1 ... N
)  |  ( p  e.  Prime  /\  p  ||  n ) }  =  { n  e.  (
1 ... N )  |  ( k  e.  Prime  /\  k  ||  n ) } )
36 prmrec.7 . . . . . . . . . . . . . . 15  |-  W  =  ( p  e.  NN  |->  { n  e.  (
1 ... N )  |  ( p  e.  Prime  /\  p  ||  n ) } )
37 ovex 6109 . . . . . . . . . . . . . . . 16  |-  ( 1 ... N )  e. 
_V
3837rabex 4357 . . . . . . . . . . . . . . 15  |-  { n  e.  ( 1 ... N
)  |  ( k  e.  Prime  /\  k  ||  n ) }  e.  _V
3935, 36, 38fvmpt 5809 . . . . . . . . . . . . . 14  |-  ( k  e.  NN  ->  ( W `  k )  =  { n  e.  ( 1 ... N )  |  ( k  e. 
Prime  /\  k  ||  n
) } )
4039adantl 454 . . . . . . . . . . . . 13  |-  ( (
ph  /\  k  e.  NN )  ->  ( W `
 k )  =  { n  e.  ( 1 ... N )  |  ( k  e. 
Prime  /\  k  ||  n
) } )
41 ssrab2 3430 . . . . . . . . . . . . 13  |-  { n  e.  ( 1 ... N
)  |  ( k  e.  Prime  /\  k  ||  n ) }  C_  ( 1 ... N
)
4240, 41syl6eqss 3400 . . . . . . . . . . . 12  |-  ( (
ph  /\  k  e.  NN )  ->  ( W `
 k )  C_  ( 1 ... N
) )
4331, 42syldan 458 . . . . . . . . . . 11  |-  ( (
ph  /\  k  e.  ( ( K  + 
1 ) ... N
) )  ->  ( W `  k )  C_  ( 1 ... N
) )
4443ralrimiva 2791 . . . . . . . . . 10  |-  ( ph  ->  A. k  e.  ( ( K  +  1 ) ... N ) ( W `  k
)  C_  ( 1 ... N ) )
45 iunss 4134 . . . . . . . . . 10  |-  ( U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) 
C_  ( 1 ... N )  <->  A. k  e.  ( ( K  + 
1 ) ... N
) ( W `  k )  C_  (
1 ... N ) )
4644, 45sylibr 205 . . . . . . . . 9  |-  ( ph  ->  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
)  C_  ( 1 ... N ) )
4726, 46unssd 3525 . . . . . . . 8  |-  ( ph  ->  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) )  C_  ( 1 ... N ) )
48 breq1 4218 . . . . . . . . . . . . . . . . . 18  |-  ( p  =  q  ->  (
p  ||  n  <->  q  ||  n ) )
4948notbid 287 . . . . . . . . . . . . . . . . 17  |-  ( p  =  q  ->  ( -.  p  ||  n  <->  -.  q  ||  n ) )
5049cbvralv 2934 . . . . . . . . . . . . . . . 16  |-  ( A. p  e.  ( Prime  \  ( 1 ... K
) )  -.  p  ||  n  <->  A. q  e.  ( Prime  \  ( 1 ... K ) )  -.  q  ||  n
)
51 breq2 4219 . . . . . . . . . . . . . . . . . 18  |-  ( n  =  x  ->  (
q  ||  n  <->  q  ||  x ) )
5251notbid 287 . . . . . . . . . . . . . . . . 17  |-  ( n  =  x  ->  ( -.  q  ||  n  <->  -.  q  ||  x ) )
5352ralbidv 2727 . . . . . . . . . . . . . . . 16  |-  ( n  =  x  ->  ( A. q  e.  ( Prime  \  ( 1 ... K ) )  -.  q  ||  n  <->  A. q  e.  ( Prime  \  (
1 ... K ) )  -.  q  ||  x
) )
5450, 53syl5bb 250 . . . . . . . . . . . . . . 15  |-  ( n  =  x  ->  ( A. p  e.  ( Prime  \  ( 1 ... K ) )  -.  p  ||  n  <->  A. q  e.  ( Prime  \  (
1 ... K ) )  -.  q  ||  x
) )
5554, 5elrab2 3096 . . . . . . . . . . . . . 14  |-  ( x  e.  M  <->  ( x  e.  ( 1 ... N
)  /\  A. q  e.  ( Prime  \  (
1 ... K ) )  -.  q  ||  x
) )
56 elun1 3516 . . . . . . . . . . . . . 14  |-  ( x  e.  M  ->  x  e.  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) ) )
5755, 56sylbir 206 . . . . . . . . . . . . 13  |-  ( ( x  e.  ( 1 ... N )  /\  A. q  e.  ( Prime  \  ( 1 ... K ) )  -.  q  ||  x )  ->  x  e.  ( M  u.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) )
5857ex 425 . . . . . . . . . . . 12  |-  ( x  e.  ( 1 ... N )  ->  ( A. q  e.  ( Prime  \  ( 1 ... K ) )  -.  q  ||  x  ->  x  e.  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) ) ) )
5958adantl 454 . . . . . . . . . . 11  |-  ( (
ph  /\  x  e.  ( 1 ... N
) )  ->  ( A. q  e.  ( Prime  \  ( 1 ... K ) )  -.  q  ||  x  ->  x  e.  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) ) ) )
60 dfrex2 2720 . . . . . . . . . . . 12  |-  ( E. q  e.  ( Prime  \  ( 1 ... K ) ) q 
||  x  <->  -.  A. q  e.  ( Prime  \  (
1 ... K ) )  -.  q  ||  x
)
61 eldifn 3472 . . . . . . . . . . . . . . . . . . . . 21  |-  ( q  e.  ( Prime  \  (
1 ... K ) )  ->  -.  q  e.  ( 1 ... K
) )
6261ad2antrl 710 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  -.  q  e.  ( 1 ... K
) )
63 eldifi 3471 . . . . . . . . . . . . . . . . . . . . . . . 24  |-  ( q  e.  ( Prime  \  (
1 ... K ) )  ->  q  e.  Prime )
6463ad2antrl 710 . . . . . . . . . . . . . . . . . . . . . . 23  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  e.  Prime )
65 prmnn 13087 . . . . . . . . . . . . . . . . . . . . . . 23  |-  ( q  e.  Prime  ->  q  e.  NN )
6664, 65syl 16 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  e.  NN )
6766, 29syl6eleq 2528 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  e.  (
ZZ>= `  1 ) )
6815nnzd 10379 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( ph  ->  K  e.  ZZ )
6968ad2antrr 708 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  K  e.  ZZ )
70 elfz5 11056 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( q  e.  ( ZZ>= ` 
1 )  /\  K  e.  ZZ )  ->  (
q  e.  ( 1 ... K )  <->  q  <_  K ) )
7167, 69, 70syl2anc 644 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  ( q  e.  ( 1 ... K
)  <->  q  <_  K
) )
7262, 71mtbid 293 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  -.  q  <_  K )
7315nnred 10020 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ph  ->  K  e.  RR )
7473ad2antrr 708 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  K  e.  RR )
7566nnred 10020 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  e.  RR )
7674, 75ltnled 9225 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  ( K  < 
q  <->  -.  q  <_  K ) )
7772, 76mpbird 225 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  K  <  q
)
78 prmz 13088 . . . . . . . . . . . . . . . . . . . 20  |-  ( q  e.  Prime  ->  q  e.  ZZ )
7964, 78syl 16 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  e.  ZZ )
80 zltp1le 10330 . . . . . . . . . . . . . . . . . . 19  |-  ( ( K  e.  ZZ  /\  q  e.  ZZ )  ->  ( K  <  q  <->  ( K  +  1 )  <_  q ) )
8169, 79, 80syl2anc 644 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  ( K  < 
q  <->  ( K  + 
1 )  <_  q
) )
8277, 81mpbid 203 . . . . . . . . . . . . . . . . 17  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  ( K  + 
1 )  <_  q
)
83 elfznn 11085 . . . . . . . . . . . . . . . . . . . 20  |-  ( x  e.  ( 1 ... N )  ->  x  e.  NN )
8483ad2antlr 709 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  x  e.  NN )
8584nnred 10020 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  x  e.  RR )
862ad2antrr 708 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  N  e.  RR )
87 simprr 735 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  ||  x
)
88 dvdsle 12900 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( q  e.  ZZ  /\  x  e.  NN )  ->  ( q  ||  x  ->  q  <_  x )
)
8979, 84, 88syl2anc 644 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  ( q  ||  x  ->  q  <_  x
) )
9087, 89mpd 15 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  <_  x
)
91 elfzle2 11066 . . . . . . . . . . . . . . . . . . 19  |-  ( x  e.  ( 1 ... N )  ->  x  <_  N )
9291ad2antlr 709 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  x  <_  N
)
9375, 85, 86, 90, 92letrd 9232 . . . . . . . . . . . . . . . . 17  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  <_  N
)
9468peano2zd 10383 . . . . . . . . . . . . . . . . . . 19  |-  ( ph  ->  ( K  +  1 )  e.  ZZ )
9594ad2antrr 708 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  ( K  + 
1 )  e.  ZZ )
961nnzd 10379 . . . . . . . . . . . . . . . . . . 19  |-  ( ph  ->  N  e.  ZZ )
9796ad2antrr 708 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  N  e.  ZZ )
98 elfz 11054 . . . . . . . . . . . . . . . . . 18  |-  ( ( q  e.  ZZ  /\  ( K  +  1
)  e.  ZZ  /\  N  e.  ZZ )  ->  ( q  e.  ( ( K  +  1 ) ... N )  <-> 
( ( K  + 
1 )  <_  q  /\  q  <_  N ) ) )
9979, 95, 97, 98syl3anc 1185 . . . . . . . . . . . . . . . . 17  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  ( q  e.  ( ( K  + 
1 ) ... N
)  <->  ( ( K  +  1 )  <_ 
q  /\  q  <_  N ) ) )
10082, 93, 99mpbir2and 890 . . . . . . . . . . . . . . . 16  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  e.  ( ( K  +  1 ) ... N ) )
101 simplr 733 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  x  e.  ( 1 ... N ) )
10264, 87jca 520 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  ( q  e. 
Prime  /\  q  ||  x
) )
10351anbi2d 686 . . . . . . . . . . . . . . . . . . 19  |-  ( n  =  x  ->  (
( q  e.  Prime  /\  q  ||  n )  <-> 
( q  e.  Prime  /\  q  ||  x ) ) )
104103elrab 3094 . . . . . . . . . . . . . . . . . 18  |-  ( x  e.  { n  e.  ( 1 ... N
)  |  ( q  e.  Prime  /\  q  ||  n ) }  <->  ( x  e.  ( 1 ... N
)  /\  ( q  e.  Prime  /\  q  ||  x ) ) )
105101, 102, 104sylanbrc 647 . . . . . . . . . . . . . . . . 17  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  x  e.  {
n  e.  ( 1 ... N )  |  ( q  e.  Prime  /\  q  ||  n ) } )
106 eleq1 2498 . . . . . . . . . . . . . . . . . . . . 21  |-  ( p  =  q  ->  (
p  e.  Prime  <->  q  e.  Prime ) )
107106, 48anbi12d 693 . . . . . . . . . . . . . . . . . . . 20  |-  ( p  =  q  ->  (
( p  e.  Prime  /\  p  ||  n )  <-> 
( q  e.  Prime  /\  q  ||  n ) ) )
108107rabbidv 2950 . . . . . . . . . . . . . . . . . . 19  |-  ( p  =  q  ->  { n  e.  ( 1 ... N
)  |  ( p  e.  Prime  /\  p  ||  n ) }  =  { n  e.  (
1 ... N )  |  ( q  e.  Prime  /\  q  ||  n ) } )
10937rabex 4357 . . . . . . . . . . . . . . . . . . 19  |-  { n  e.  ( 1 ... N
)  |  ( q  e.  Prime  /\  q  ||  n ) }  e.  _V
110108, 36, 109fvmpt 5809 . . . . . . . . . . . . . . . . . 18  |-  ( q  e.  NN  ->  ( W `  q )  =  { n  e.  ( 1 ... N )  |  ( q  e. 
Prime  /\  q  ||  n
) } )
11166, 110syl 16 . . . . . . . . . . . . . . . . 17  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  ( W `  q )  =  {
n  e.  ( 1 ... N )  |  ( q  e.  Prime  /\  q  ||  n ) } )
112105, 111eleqtrrd 2515 . . . . . . . . . . . . . . . 16  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  x  e.  ( W `  q ) )
113 fveq2 5731 . . . . . . . . . . . . . . . . . 18  |-  ( k  =  q  ->  ( W `  k )  =  ( W `  q ) )
114113eleq2d 2505 . . . . . . . . . . . . . . . . 17  |-  ( k  =  q  ->  (
x  e.  ( W `
 k )  <->  x  e.  ( W `  q ) ) )
115114rspcev 3054 . . . . . . . . . . . . . . . 16  |-  ( ( q  e.  ( ( K  +  1 ) ... N )  /\  x  e.  ( W `  q ) )  ->  E. k  e.  (
( K  +  1 ) ... N ) x  e.  ( W `
 k ) )
116100, 112, 115syl2anc 644 . . . . . . . . . . . . . . 15  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  E. k  e.  ( ( K  +  1 ) ... N ) x  e.  ( W `
 k ) )
117 eliun 4099 . . . . . . . . . . . . . . 15  |-  ( x  e.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k )  <->  E. k  e.  ( ( K  + 
1 ) ... N
) x  e.  ( W `  k ) )
118116, 117sylibr 205 . . . . . . . . . . . . . 14  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  x  e.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) )
119 elun2 3517 . . . . . . . . . . . . . 14  |-  ( x  e.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k )  ->  x  e.  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) ) )
120118, 119syl 16 . . . . . . . . . . . . 13  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  x  e.  ( M  u.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) )
121120rexlimdvaa 2833 . . . . . . . . . . . 12  |-  ( (
ph  /\  x  e.  ( 1 ... N
) )  ->  ( E. q  e.  ( Prime  \  ( 1 ... K ) ) q 
||  x  ->  x  e.  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) ) ) )
12260, 121syl5bir 211 . . . . . . . . . . 11  |-  ( (
ph  /\  x  e.  ( 1 ... N
) )  ->  ( -.  A. q  e.  ( Prime  \  ( 1 ... K ) )  -.  q  ||  x  ->  x  e.  ( M  u.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) ) )
12359, 122pm2.61d 153 . . . . . . . . . 10  |-  ( (
ph  /\  x  e.  ( 1 ... N
) )  ->  x  e.  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) ) )
124123ex 425 . . . . . . . . 9  |-  ( ph  ->  ( x  e.  ( 1 ... N )  ->  x  e.  ( M  u.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) ) )
125124ssrdv 3356 . . . . . . . 8  |-  ( ph  ->  ( 1 ... N
)  C_  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) ) )
12647, 125eqssd 3367 . . . . . . 7  |-  ( ph  ->  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) )  =  ( 1 ... N ) )
127126fveq2d 5735 . . . . . 6  |-  ( ph  ->  ( # `  ( M  u.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) )  =  ( # `  (
1 ... N ) ) )
1281nnnn0d 10279 . . . . . . 7  |-  ( ph  ->  N  e.  NN0 )
129 hashfz1 11635 . . . . . . 7  |-  ( N  e.  NN0  ->  ( # `  ( 1 ... N
) )  =  N )
130128, 129syl 16 . . . . . 6  |-  ( ph  ->  ( # `  (
1 ... N ) )  =  N )
131127, 130eqtr2d 2471 . . . . 5  |-  ( ph  ->  N  =  ( # `  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) ) ) )
1329a1i 11 . . . . . 6  |-  ( ph  ->  M  e.  Fin )
133 ssfi 7332 . . . . . . 7  |-  ( ( ( 1 ... N
)  e.  Fin  /\  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) 
C_  ( 1 ... N ) )  ->  U_ k  e.  (
( K  +  1 ) ... N ) ( W `  k
)  e.  Fin )
1344, 46, 133sylancr 646 . . . . . 6  |-  ( ph  ->  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
)  e.  Fin )
135 simprr 735 . . . . . . . . . . . . . . . . 17  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  k  e.  Prime )
136 noel 3634 . . . . . . . . . . . . . . . . . 18  |-  -.  k  e.  (/)
137 simprl 734 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  k  e.  ( ( K  +  1 ) ... N ) )
138137biantrud 495 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  ( k  e.  ( 1 ... K
)  <->  ( k  e.  ( 1 ... K
)  /\  k  e.  ( ( K  + 
1 ) ... N
) ) ) )
139 elin 3532 . . . . . . . . . . . . . . . . . . . 20  |-  ( k  e.  ( ( 1 ... K )  i^i  ( ( K  + 
1 ) ... N
) )  <->  ( k  e.  ( 1 ... K
)  /\  k  e.  ( ( K  + 
1 ) ... N
) ) )
140138, 139syl6bbr 256 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  ( k  e.  ( 1 ... K
)  <->  k  e.  ( ( 1 ... K
)  i^i  ( ( K  +  1 ) ... N ) ) ) )
14173ltp1d 9946 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( ph  ->  K  <  ( K  +  1 ) )
142 fzdisj 11083 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( K  <  ( K  + 
1 )  ->  (
( 1 ... K
)  i^i  ( ( K  +  1 ) ... N ) )  =  (/) )
143141, 142syl 16 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ph  ->  ( ( 1 ... K )  i^i  (
( K  +  1 ) ... N ) )  =  (/) )
144143ad2antrr 708 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  ( ( 1 ... K )  i^i  ( ( K  + 
1 ) ... N
) )  =  (/) )
145144eleq2d 2505 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  ( k  e.  ( ( 1 ... K )  i^i  (
( K  +  1 ) ... N ) )  <->  k  e.  (/) ) )
146140, 145bitrd 246 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  ( k  e.  ( 1 ... K
)  <->  k  e.  (/) ) )
147136, 146mtbiri 296 . . . . . . . . . . . . . . . . 17  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  -.  k  e.  ( 1 ... K
) )
148135, 147eldifd 3333 . . . . . . . . . . . . . . . 16  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  k  e.  ( Prime  \  ( 1 ... K ) ) )
149 breq2 4219 . . . . . . . . . . . . . . . . . . . . 21  |-  ( n  =  x  ->  (
p  ||  n  <->  p  ||  x
) )
150149notbid 287 . . . . . . . . . . . . . . . . . . . 20  |-  ( n  =  x  ->  ( -.  p  ||  n  <->  -.  p  ||  x ) )
151150ralbidv 2727 . . . . . . . . . . . . . . . . . . 19  |-  ( n  =  x  ->  ( A. p  e.  ( Prime  \  ( 1 ... K ) )  -.  p  ||  n  <->  A. p  e.  ( Prime  \  (
1 ... K ) )  -.  p  ||  x
) )
152151, 5elrab2 3096 . . . . . . . . . . . . . . . . . 18  |-  ( x  e.  M  <->  ( x  e.  ( 1 ... N
)  /\  A. p  e.  ( Prime  \  (
1 ... K ) )  -.  p  ||  x
) )
153152simprbi 452 . . . . . . . . . . . . . . . . 17  |-  ( x  e.  M  ->  A. p  e.  ( Prime  \  (
1 ... K ) )  -.  p  ||  x
)
154153ad2antlr 709 . . . . . . . . . . . . . . . 16  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  A. p  e.  ( Prime  \  ( 1 ... K ) )  -.  p  ||  x
)
155 breq1 4218 . . . . . . . . . . . . . . . . . 18  |-  ( p  =  k  ->  (
p  ||  x  <->  k  ||  x ) )
156155notbid 287 . . . . . . . . . . . . . . . . 17  |-  ( p  =  k  ->  ( -.  p  ||  x  <->  -.  k  ||  x ) )
157156rspcv 3050 . . . . . . . . . . . . . . . 16  |-  ( k  e.  ( Prime  \  (
1 ... K ) )  ->  ( A. p  e.  ( Prime  \  (
1 ... K ) )  -.  p  ||  x  ->  -.  k  ||  x
) )
158148, 154, 157sylc 59 . . . . . . . . . . . . . . 15  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  -.  k  ||  x )
159158expr 600 . . . . . . . . . . . . . 14  |-  ( ( ( ph  /\  x  e.  M )  /\  k  e.  ( ( K  + 
1 ) ... N
) )  ->  (
k  e.  Prime  ->  -.  k  ||  x ) )
160 imnan 413 . . . . . . . . . . . . . 14  |-  ( ( k  e.  Prime  ->  -.  k  ||  x )  <->  -.  ( k  e.  Prime  /\  k  ||  x ) )
161159, 160sylib 190 . . . . . . . . . . . . 13  |-  ( ( ( ph  /\  x  e.  M )  /\  k  e.  ( ( K  + 
1 ) ... N
) )  ->  -.  ( k  e.  Prime  /\  k  ||  x ) )
16231adantlr 697 . . . . . . . . . . . . . . . 16  |-  ( ( ( ph  /\  x  e.  M )  /\  k  e.  ( ( K  + 
1 ) ... N
) )  ->  k  e.  NN )
163162, 39syl 16 . . . . . . . . . . . . . . 15  |-  ( ( ( ph  /\  x  e.  M )  /\  k  e.  ( ( K  + 
1 ) ... N
) )  ->  ( W `  k )  =  { n  e.  ( 1 ... N )  |  ( k  e. 
Prime  /\  k  ||  n
) } )
164163eleq2d 2505 . . . . . . . . . . . . . 14  |-  ( ( ( ph  /\  x  e.  M )  /\  k  e.  ( ( K  + 
1 ) ... N
) )  ->  (
x  e.  ( W `
 k )  <->  x  e.  { n  e.  ( 1 ... N )  |  ( k  e.  Prime  /\  k  ||  n ) } ) )
165 breq2 4219 . . . . . . . . . . . . . . . . 17  |-  ( n  =  x  ->  (
k  ||  n  <->  k  ||  x ) )
166165anbi2d 686 . . . . . . . . . . . . . . . 16  |-  ( n  =  x  ->  (
( k  e.  Prime  /\  k  ||  n )  <-> 
( k  e.  Prime  /\  k  ||  x ) ) )
167166elrab 3094 . . . . . . . . . . . . . . 15  |-  ( x  e.  { n  e.  ( 1 ... N
)  |  ( k  e.  Prime  /\  k  ||  n ) }  <->  ( x  e.  ( 1 ... N
)  /\  ( k  e.  Prime  /\  k  ||  x ) ) )
168167simprbi 452 . . . . . . . . . . . . . 14  |-  ( x  e.  { n  e.  ( 1 ... N
)  |  ( k  e.  Prime  /\  k  ||  n ) }  ->  ( k  e.  Prime  /\  k  ||  x ) )
169164, 168syl6bi 221 . . . . . . . . . . . . 13  |-  ( ( ( ph  /\  x  e.  M )  /\  k  e.  ( ( K  + 
1 ) ... N
) )  ->  (
x  e.  ( W `
 k )  -> 
( k  e.  Prime  /\  k  ||  x ) ) )
170161, 169mtod 171 . . . . . . . . . . . 12  |-  ( ( ( ph  /\  x  e.  M )  /\  k  e.  ( ( K  + 
1 ) ... N
) )  ->  -.  x  e.  ( W `  k ) )
171170nrexdv 2811 . . . . . . . . . . 11  |-  ( (
ph  /\  x  e.  M )  ->  -.  E. k  e.  ( ( K  +  1 ) ... N ) x  e.  ( W `  k ) )
172171, 117sylnibr 298 . . . . . . . . . 10  |-  ( (
ph  /\  x  e.  M )  ->  -.  x  e.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) )
173172ex 425 . . . . . . . . 9  |-  ( ph  ->  ( x  e.  M  ->  -.  x  e.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) ) )
174 imnan 413 . . . . . . . . 9  |-  ( ( x  e.  M  ->  -.  x  e.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) )  <->  -.  (
x  e.  M  /\  x  e.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) )
175173, 174sylib 190 . . . . . . . 8  |-  ( ph  ->  -.  ( x  e.  M  /\  x  e. 
U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) ) )
176 elin 3532 . . . . . . . 8  |-  ( x  e.  ( M  i^i  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) )  <->  ( x  e.  M  /\  x  e. 
U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) ) )
177175, 176sylnibr 298 . . . . . . 7  |-  ( ph  ->  -.  x  e.  ( M  i^i  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) )
178177eq0rdv 3664 . . . . . 6  |-  ( ph  ->  ( M  i^i  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) )  =  (/) )
179 hashun 11661 . . . . . 6  |-  ( ( M  e.  Fin  /\  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k )  e.  Fin  /\  ( M  i^i  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) )  =  (/) )  ->  ( # `  ( M  u.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) )  =  ( ( # `  M )  +  (
# `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) ) )
180132, 134, 178, 179syl3anc 1185 . . . . 5  |-  ( ph  ->  ( # `  ( M  u.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) )  =  ( ( # `  M )  +  (
# `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) ) )
18125, 131, 1803eqtrd 2474 . . . 4  |-  ( ph  ->  ( ( N  / 
2 )  +  ( N  /  2 ) )  =  ( (
# `  M )  +  ( # `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) ) )
182 hashcl 11644 . . . . . . 7  |-  ( U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k )  e.  Fin  ->  ( # `
 U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) )  e.  NN0 )
183134, 182syl 16 . . . . . 6  |-  ( ph  ->  ( # `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) )  e. 
NN0 )
184183nn0red 10280 . . . . 5  |-  ( ph  ->  ( # `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) )  e.  RR )
185 fzfid 11317 . . . . . . . 8  |-  ( ph  ->  ( ( K  + 
1 ) ... N
)  e.  Fin )
18627, 30sylan 459 . . . . . . . . . 10  |-  ( (
ph  /\  k  e.  ( ZZ>= `  ( K  +  1 ) ) )  ->  k  e.  NN )
187 nnrecre 10041 . . . . . . . . . . 11  |-  ( k  e.  NN  ->  (
1  /  k )  e.  RR )
188 0re 9096 . . . . . . . . . . 11  |-  0  e.  RR
189 ifcl 3777 . . . . . . . . . . 11  |-  ( ( ( 1  /  k
)  e.  RR  /\  0  e.  RR )  ->  if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 )  e.  RR )
190187, 188, 189sylancl 645 . . . . . . . . . 10  |-  ( k  e.  NN  ->  if ( k  e.  Prime ,  ( 1  /  k
) ,  0 )  e.  RR )
191186, 190syl 16 . . . . . . . . 9  |-  ( (
ph  /\  k  e.  ( ZZ>= `  ( K  +  1 ) ) )  ->  if (
k  e.  Prime ,  ( 1  /  k ) ,  0 )  e.  RR )
19228, 191sylan2 462 . . . . . . . 8  |-  ( (
ph  /\  k  e.  ( ( K  + 
1 ) ... N
) )  ->  if ( k  e.  Prime ,  ( 1  /  k
) ,  0 )  e.  RR )
193185, 192fsumrecl 12533 . . . . . . 7  |-  ( ph  -> 
sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 )  e.  RR )
1942, 193remulcld 9121 . . . . . 6  |-  ( ph  ->  ( N  x.  sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) )  e.  RR )
195 prmrec.1 . . . . . . . 8  |-  F  =  ( n  e.  NN  |->  if ( n  e.  Prime ,  ( 1  /  n
) ,  0 ) )
196 prmrec.5 . . . . . . . 8  |-  ( ph  ->  seq  1 (  +  ,  F )  e. 
dom 
~~>  )
197 prmrec.6 . . . . . . . 8  |-  ( ph  -> 
sum_ k  e.  (
ZZ>= `  ( K  + 
1 ) ) if ( k  e.  Prime ,  ( 1  /  k
) ,  0 )  <  ( 1  / 
2 ) )
198195, 15, 1, 5, 196, 197, 36prmreclem4 13292 . . . . . . 7  |-  ( ph  ->  ( N  e.  (
ZZ>= `  K )  -> 
( # `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) )  <_ 
( N  x.  sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) ) ) )
199 eluz 10504 . . . . . . . . . 10  |-  ( ( N  e.  ZZ  /\  K  e.  ZZ )  ->  ( K  e.  (
ZZ>= `  N )  <->  N  <_  K ) )
20096, 68, 199syl2anc 644 . . . . . . . . 9  |-  ( ph  ->  ( K  e.  (
ZZ>= `  N )  <->  N  <_  K ) )
201 nnleltp1 10334 . . . . . . . . . 10  |-  ( ( N  e.  NN  /\  K  e.  NN )  ->  ( N  <_  K  <->  N  <  ( K  + 
1 ) ) )
2021, 15, 201syl2anc 644 . . . . . . . . 9  |-  ( ph  ->  ( N  <_  K  <->  N  <  ( K  + 
1 ) ) )
203 fzn 11076 . . . . . . . . . 10  |-  ( ( ( K  +  1 )  e.  ZZ  /\  N  e.  ZZ )  ->  ( N  <  ( K  +  1 )  <-> 
( ( K  + 
1 ) ... N
)  =  (/) ) )
20494, 96, 203syl2anc 644 . . . . . . . . 9  |-  ( ph  ->  ( N  <  ( K  +  1 )  <-> 
( ( K  + 
1 ) ... N
)  =  (/) ) )
205200, 202, 2043bitrd 272 . . . . . . . 8  |-  ( ph  ->  ( K  e.  (
ZZ>= `  N )  <->  ( ( K  +  1 ) ... N )  =  (/) ) )
206 0le0 10086 . . . . . . . . . 10  |-  0  <_  0
20724mul01d 9270 . . . . . . . . . 10  |-  ( ph  ->  ( N  x.  0 )  =  0 )
208206, 207syl5breqr 4251 . . . . . . . . 9  |-  ( ph  ->  0  <_  ( N  x.  0 ) )
209 iuneq1 4108 . . . . . . . . . . . . 13  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k )  =  U_ k  e.  (/)  ( W `
 k ) )
210 0iun 4150 . . . . . . . . . . . . 13  |-  U_ k  e.  (/)  ( W `  k )  =  (/)
211209, 210syl6eq 2486 . . . . . . . . . . . 12  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k )  =  (/) )
212211fveq2d 5735 . . . . . . . . . . 11  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  ( # `  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) )  =  (
# `  (/) ) )
213 hash0 11651 . . . . . . . . . . 11  |-  ( # `  (/) )  =  0
214212, 213syl6eq 2486 . . . . . . . . . 10  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  ( # `  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) )  =  0 )
215 sumeq1 12488 . . . . . . . . . . . 12  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  sum_ k  e.  ( ( K  + 
1 ) ... N
) if ( k  e.  Prime ,  ( 1  /  k ) ,  0 )  =  sum_ k  e.  (/)  if ( k  e.  Prime ,  ( 1  /  k ) ,  0 ) )
216 sum0 12520 . . . . . . . . . . . 12  |-  sum_ k  e.  (/)  if ( k  e.  Prime ,  ( 1  /  k ) ,  0 )  =  0
217215, 216syl6eq 2486 . . . . . . . . . . 11  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  sum_ k  e.  ( ( K  + 
1 ) ... N
) if ( k  e.  Prime ,  ( 1  /  k ) ,  0 )  =  0 )
218217oveq2d 6100 . . . . . . . . . 10  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  ( N  x.  sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 ) )  =  ( N  x.  0 ) )
219214, 218breq12d 4228 . . . . . . . . 9  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  ( (
# `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) )  <_ 
( N  x.  sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) )  <->  0  <_  ( N  x.  0 ) ) )
220208, 219syl5ibrcom 215 . . . . . . . 8  |-  ( ph  ->  ( ( ( K  +  1 ) ... N )  =  (/)  ->  ( # `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) )  <_ 
( N  x.  sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) ) ) )
221205, 220sylbid 208 . . . . . . 7  |-  ( ph  ->  ( K  e.  (
ZZ>= `  N )  -> 
( # `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) )  <_ 
( N  x.  sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) ) ) )
222 uztric 10512 . . . . . . . 8  |-  ( ( K  e.  ZZ  /\  N  e.  ZZ )  ->  ( N  e.  (
ZZ>= `  K )  \/  K  e.  ( ZZ>= `  N ) ) )
22368, 96, 222syl2anc 644 . . . . . . 7  |-  ( ph  ->  ( N  e.  (
ZZ>= `  K )  \/  K  e.  ( ZZ>= `  N ) ) )
224198, 221, 223mpjaod 372 . . . . . 6  |-  ( ph  ->  ( # `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) )  <_ 
( N  x.  sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) ) )
225 eqid 2438 . . . . . . . . . 10  |-  ( ZZ>= `  ( K  +  1
) )  =  (
ZZ>= `  ( K  + 
1 ) )
226 eleq1 2498 . . . . . . . . . . . . 13  |-  ( n  =  k  ->  (
n  e.  Prime  <->  k  e.  Prime ) )
227 oveq2 6092 . . . . . . . . . . . . 13  |-  ( n  =  k  ->  (
1  /  n )  =  ( 1  / 
k ) )
228 eqidd 2439 . . . . . . . . . . . . 13  |-  ( n  =  k  ->  0  =  0 )
229226, 227, 228ifbieq12d 3763 . . . . . . . . . . . 12  |-  ( n  =  k  ->  if ( n  e.  Prime ,  ( 1  /  n
) ,  0 )  =  if ( k  e.  Prime ,  ( 1  /  k ) ,  0 ) )
230 ovex 6109 . . . . . . . . . . . . 13  |-  ( 1  /  k )  e. 
_V
231 c0ex 9090 . . . . . . . . . . . . 13  |-  0  e.  _V
232230, 231ifex 3799 . . . . . . . . . . . 12  |-  if ( k  e.  Prime ,  ( 1  /  k ) ,  0 )  e. 
_V
233229, 195, 232fvmpt 5809 . . . . . . . . . . 11  |-  ( k  e.  NN  ->  ( F `  k )  =  if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 ) )
234186, 233syl 16 . . . . . . . . . 10  |-  ( (
ph  /\  k  e.  ( ZZ>= `  ( K  +  1 ) ) )  ->  ( F `  k )  =  if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) )
235190recnd 9119 . . . . . . . . . . . . . 14  |-  ( k  e.  NN  ->  if ( k  e.  Prime ,  ( 1  /  k
) ,  0 )  e.  CC )
236233, 235eqeltrd 2512 . . . . . . . . . . . . 13  |-  ( k  e.  NN  ->  ( F `  k )  e.  CC )
237236adantl 454 . . . . . . . . . . . 12  |-  ( (
ph  /\  k  e.  NN )  ->  ( F `
 k )  e.  CC )
23829, 27, 237iserex 12455 . . . . . . . . . . 11  |-  ( ph  ->  (  seq  1 (  +  ,  F )  e.  dom  ~~>  <->  seq  ( K  +  1 ) (  +  ,  F )  e.  dom  ~~>  ) )
239196, 238mpbid 203 . . . . . . . . . 10  |-  ( ph  ->  seq  ( K  + 
1 ) (  +  ,  F )  e. 
dom 
~~>  )
240225, 94, 234, 191, 239isumrecl 12554 . . . . . . . . 9  |-  ( ph  -> 
sum_ k  e.  (
ZZ>= `  ( K  + 
1 ) ) if ( k  e.  Prime ,  ( 1  /  k
) ,  0 )  e.  RR )
241 1re 9095 . . . . . . . . . . 11  |-  1  e.  RR
242241rehalfcli 10221 . . . . . . . . . 10  |-  ( 1  /  2 )  e.  RR
243242a1i 11 . . . . . . . . 9  |-  ( ph  ->  ( 1  /  2
)  e.  RR )
244 fzssuz 11098 . . . . . . . . . . 11  |-  ( ( K  +  1 ) ... N )  C_  ( ZZ>= `  ( K  +  1 ) )
245244a1i 11 . . . . . . . . . 10  |-  ( ph  ->  ( ( K  + 
1 ) ... N
)  C_  ( ZZ>= `  ( K  +  1
) ) )
246 nnrp 10626 . . . . . . . . . . . . . 14  |-  ( k  e.  NN  ->  k  e.  RR+ )
247246rpreccld 10663 . . . . . . . . . . . . 13  |-  ( k  e.  NN  ->  (
1  /  k )  e.  RR+ )
248247rpge0d 10657 . . . . . . . . . . . 12  |-  ( k  e.  NN  ->  0  <_  ( 1  /  k
) )
249 breq2 4219 . . . . . . . . . . . . 13  |-  ( ( 1  /  k )  =  if ( k  e.  Prime ,  ( 1  /  k ) ,  0 )  ->  (
0  <_  ( 1  /  k )  <->  0  <_  if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) ) )
250 breq2 4219 . . . . . . . . . . . . 13  |-  ( 0  =  if ( k  e.  Prime ,  ( 1  /  k ) ,  0 )  ->  (
0  <_  0  <->  0  <_  if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) ) )
251249, 250ifboth 3772 . . . . . . . . . . . 12  |-  ( ( 0  <_  ( 1  /  k )  /\  0  <_  0 )  -> 
0  <_  if (
k  e.  Prime ,  ( 1  /  k ) ,  0 ) )
252248, 206, 251sylancl 645 . . . . . . . . . . 11  |-  ( k  e.  NN  ->  0  <_  if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 ) )
253186, 252syl 16 . . . . . . . . . 10  |-  ( (
ph  /\  k  e.  ( ZZ>= `  ( K  +  1 ) ) )  ->  0  <_  if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) )
254225, 94, 185, 245, 234, 191, 253, 239isumless 12630 . . . . . . . . 9  |-  ( ph  -> 
sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 )  <_  sum_ k  e.  ( ZZ>= `  ( K  +  1 ) ) if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 ) )
255193, 240, 243, 254, 197lelttrd 9233 . . . . . . . 8  |-  ( ph  -> 
sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 )  <  (
1  /  2 ) )
2561nngt0d 10048 . . . . . . . . 9  |-  ( ph  ->  0  <  N )
257 ltmul2 9866 . . . . . . . . 9  |-  ( (
sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 )  e.  RR  /\  ( 1  /  2
)  e.  RR  /\  ( N  e.  RR  /\  0  <  N ) )  ->  ( sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e.  Prime ,  ( 1  /  k
) ,  0 )  <  ( 1  / 
2 )  <->  ( N  x.  sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 ) )  < 
( N  x.  (
1  /  2 ) ) ) )
258193, 243, 2, 256, 257syl112anc 1189 . . . . . . . 8  |-  ( ph  ->  ( sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 )  <  (
1  /  2 )  <-> 
( N  x.  sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) )  <  ( N  x.  ( 1  / 
2 ) ) ) )
259255, 258mpbid 203 . . . . . . 7  |-  ( ph  ->  ( N  x.  sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) )  <  ( N  x.  ( 1  / 
2 ) ) )
260 2cn 10075 . . . . . . . . 9  |-  2  e.  CC
261 2ne0 10088 . . . . . . . . 9  |-  2  =/=  0
262 divrec 9699 . . . . . . . . 9  |-  ( ( N  e.  CC  /\  2  e.  CC  /\  2  =/=  0 )  ->  ( N  /  2 )  =  ( N  x.  (
1  /  2 ) ) )
263260, 261, 262mp3an23 1272 . . . . . . . 8  |-  ( N  e.  CC  ->  ( N  /  2 )  =  ( N  x.  (
1  /  2 ) ) )
26424, 263syl 16 . . . . . . 7  |-  ( ph  ->  ( N  /  2
)  =  ( N  x.  ( 1  / 
2 ) ) )
265259, 264breqtrrd 4241 . . . . . 6  |-  ( ph  ->  ( N  x.  sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) )  <  ( N  /  2 ) )
266184, 194, 3, 224, 265lelttrd 9233 . . . . 5  |-  ( ph  ->  ( # `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) )  < 
( N  /  2
) )
267184, 3, 13, 266ltadd2dd 9234 . . . 4  |-  ( ph  ->  ( ( # `  M
)  +  ( # `  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) ) )  < 
( ( # `  M
)  +  ( N  /  2 ) ) )
268181, 267eqbrtrd 4235 . . 3  |-  ( ph  ->  ( ( N  / 
2 )  +  ( N  /  2 ) )  <  ( (
# `  M )  +  ( N  / 
2 ) ) )
2693, 13, 3ltadd1d 9624 . . 3  |-  ( ph  ->  ( ( N  / 
2 )  <  ( # `
 M )  <->  ( ( N  /  2 )  +  ( N  /  2
) )  <  (
( # `  M )  +  ( N  / 
2 ) ) ) )
270268, 269mpbird 225 . 2  |-  ( ph  ->  ( N  /  2
)  <  ( # `  M
) )
271 oveq1 6091 . . . . . . . 8  |-  ( k  =  r  ->  (
k ^ 2 )  =  ( r ^
2 ) )
272271breq1d 4225 . . . . . . 7  |-  ( k  =  r  ->  (
( k ^ 2 )  ||  x  <->  ( r ^ 2 )  ||  x ) )
273272cbvrabv 2957 . . . . . 6  |-  { k  e.  NN  |  ( k ^ 2 ) 
||  x }  =  { r  e.  NN  |  ( r ^
2 )  ||  x }
274 breq2 4219 . . . . . . 7  |-  ( x  =  n  ->  (
( r ^ 2 )  ||  x  <->  ( r ^ 2 )  ||  n ) )
275274rabbidv 2950 . . . . . 6  |-  ( x  =  n  ->  { r  e.  NN  |  ( r ^ 2 ) 
||  x }  =  { r  e.  NN  |  ( r ^
2 )  ||  n } )
276273, 275syl5eq 2482 . . . . 5  |-  ( x  =  n  ->  { k  e.  NN  |  ( k ^ 2 ) 
||  x }  =  { r  e.  NN  |  ( r ^
2 )  ||  n } )
277276supeq1d 7454 . . . 4  |-  ( x  =  n  ->  sup ( { k  e.  NN  |  ( k ^
2 )  ||  x } ,  RR ,  <  )  =  sup ( { r  e.  NN  |  ( r ^
2 )  ||  n } ,  RR ,  <  ) )
278277cbvmptv 4303 . . 3  |-  ( x  e.  NN  |->  sup ( { k  e.  NN  |  ( k ^
2 )  ||  x } ,  RR ,  <  ) )  =  ( n  e.  NN  |->  sup ( { r  e.  NN  |  ( r ^ 2 )  ||  n } ,  RR ,  <  ) )
279195, 15, 1, 5, 278prmreclem3 13291 . 2  |-  ( ph  ->  ( # `  M
)  <_  ( (
2 ^ K )  x.  ( sqr `  N
) ) )
2803, 13, 23, 270, 279ltletrd 9235 1  |-  ( ph  ->  ( N  /  2
)  <  ( (
2 ^ K )  x.  ( sqr `  N
) ) )
Colors of variables: wff set class
Syntax hints:   -. wn 3    -> wi 4    <-> wb 178    \/ wo 359    /\ wa 360    = wceq 1653    e. wcel 1726    =/= wne 2601   A.wral 2707   E.wrex 2708   {crab 2711    \ cdif 3319    u. cun 3320    i^i cin 3321    C_ wss 3322   (/)c0 3630   ifcif 3741   U_ciun 4095   class class class wbr 4215    e. cmpt 4269   dom cdm 4881   ` cfv 5457  (class class class)co 6084   Fincfn 7112   supcsup 7448   CCcc 8993   RRcr 8994   0cc0 8995   1c1 8996    + caddc 8998    x. cmul 9000    < clt 9125    <_ cle 9126    / cdiv 9682   NNcn 10005   2c2 10054   NN0cn0 10226   ZZcz 10287   ZZ>=cuz 10493   ...cfz 11048    seq cseq 11328   ^cexp 11387   #chash 11623   sqrcsqr 12043    ~~> cli 12283   sum_csu 12484    || cdivides 12857   Primecprime 13084
This theorem is referenced by:  prmreclem6  13294
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1556  ax-5 1567  ax-17 1627  ax-9 1667  ax-8 1688  ax-13 1728  ax-14 1730  ax-6 1745  ax-7 1750  ax-11 1762  ax-12 1951  ax-ext 2419  ax-rep 4323  ax-sep 4333  ax-nul 4341  ax-pow 4380  ax-pr 4406  ax-un 4704  ax-inf2 7599  ax-cnex 9051  ax-resscn 9052  ax-1cn 9053  ax-icn 9054  ax-addcl 9055  ax-addrcl 9056  ax-mulcl 9057  ax-mulrcl 9058  ax-mulcom 9059  ax-addass 9060  ax-mulass 9061  ax-distr 9062  ax-i2m1 9063  ax-1ne0 9064  ax-1rid 9065  ax-rnegex 9066  ax-rrecex 9067  ax-cnre 9068  ax-pre-lttri 9069  ax-pre-lttrn 9070  ax-pre-ltadd 9071  ax-pre-mulgt0 9072  ax-pre-sup 9073
This theorem depends on definitions:  df-bi 179  df-or 361  df-an 362  df-3or 938  df-3an 939  df-tru 1329  df-ex 1552  df-nf 1555  df-sb 1660  df-eu 2287  df-mo 2288  df-clab 2425  df-cleq 2431  df-clel 2434  df-nfc 2563  df-ne 2603  df-nel 2604  df-ral 2712  df-rex 2713  df-reu 2714  df-rmo 2715  df-rab 2716  df-v 2960  df-sbc 3164  df-csb 3254  df-dif 3325  df-un 3327  df-in 3329  df-ss 3336  df-pss 3338  df-nul 3631  df-if 3742  df-pw 3803  df-sn 3822  df-pr 3823  df-tp 3824  df-op 3825  df-uni 4018  df-int 4053  df-iun 4097  df-br 4216  df-opab 4270  df-mpt 4271  df-tr 4306  df-eprel 4497  df-id 4501  df-po 4506  df-so 4507  df-fr 4544  df-se 4545  df-we 4546  df-ord 4587  df-on 4588  df-lim 4589  df-suc 4590  df-om 4849  df-xp 4887  df-rel 4888  df-cnv 4889  df-co 4890  df-dm 4891  df-rn 4892  df-res 4893  df-ima 4894  df-iota 5421  df-fun 5459  df-fn 5460  df-f 5461  df-f1 5462  df-fo 5463  df-f1o 5464  df-fv 5465  df-isom 5466  df-ov 6087  df-oprab 6088  df-mpt2 6089  df-1st 6352  df-2nd 6353  df-riota 6552  df-recs 6636  df-rdg 6671  df-1o 6727  df-2o 6728  df-oadd 6731  df-er 6908  df-map 7023  df-pm 7024  df-en 7113  df-dom 7114  df-sdom 7115  df-fin 7116  df-sup 7449  df-oi 7482  df-card 7831  df-cda 8053  df-pnf 9127  df-mnf 9128  df-xr 9129  df-ltxr 9130  df-le 9131  df-sub 9298  df-neg 9299  df-div 9683  df-nn 10006  df-2 10063  df-3 10064  df-n0 10227  df-z 10288  df-uz 10494  df-q 10580  df-rp 10618  df-fz 11049  df-fzo 11141  df-fl 11207  df-mod 11256  df-seq 11329  df-exp 11388  df-hash 11624  df-cj 11909  df-re 11910  df-im 11911  df-sqr 12045  df-abs 12046  df-clim 12287  df-rlim 12288  df-sum 12485  df-dvds 12858  df-gcd 13012  df-prm 13085  df-pc 13216
  Copyright terms: Public domain W3C validator