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

Theorem prmreclem5 13175
Description: Lemma for prmrec 13177. 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 13174 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 9908 . . 3  |-  ( ph  ->  N  e.  RR )
32rehalfcld 10107 . 2  |-  ( ph  ->  ( N  /  2
)  e.  RR )
4 fzfi 11198 . . . . . 6  |-  ( 1 ... N )  e. 
Fin
5 prmrec.4 . . . . . . 7  |-  M  =  { n  e.  ( 1 ... N )  |  A. p  e.  ( Prime  \  (
1 ... K ) )  -.  p  ||  n }
6 ssrab2 3344 . . . . . . 7  |-  { n  e.  ( 1 ... N
)  |  A. p  e.  ( Prime  \  (
1 ... K ) )  -.  p  ||  n }  C_  ( 1 ... N )
75, 6eqsstri 3294 . . . . . 6  |-  M  C_  ( 1 ... N
)
8 ssfi 7226 . . . . . 6  |-  ( ( ( 1 ... N
)  e.  Fin  /\  M  C_  ( 1 ... N ) )  ->  M  e.  Fin )
94, 7, 8mp2an 653 . . . . 5  |-  M  e. 
Fin
10 hashcl 11526 . . . . 5  |-  ( M  e.  Fin  ->  ( # `
 M )  e. 
NN0 )
119, 10ax-mp 8 . . . 4  |-  ( # `  M )  e.  NN0
1211nn0rei 10125 . . 3  |-  ( # `  M )  e.  RR
1312a1i 10 . 2  |-  ( ph  ->  ( # `  M
)  e.  RR )
14 2nn 10026 . . . . 5  |-  2  e.  NN
15 prmrec.2 . . . . . 6  |-  ( ph  ->  K  e.  NN )
1615nnnn0d 10167 . . . . 5  |-  ( ph  ->  K  e.  NN0 )
17 nnexpcl 11281 . . . . 5  |-  ( ( 2  e.  NN  /\  K  e.  NN0 )  -> 
( 2 ^ K
)  e.  NN )
1814, 16, 17sylancr 644 . . . 4  |-  ( ph  ->  ( 2 ^ K
)  e.  NN )
1918nnred 9908 . . 3  |-  ( ph  ->  ( 2 ^ K
)  e.  RR )
201nnrpd 10540 . . . . 5  |-  ( ph  ->  N  e.  RR+ )
2120rpsqrcld 12101 . . . 4  |-  ( ph  ->  ( sqr `  N
)  e.  RR+ )
2221rpred 10541 . . 3  |-  ( ph  ->  ( sqr `  N
)  e.  RR )
2319, 22remulcld 9010 . 2  |-  ( ph  ->  ( ( 2 ^ K )  x.  ( sqr `  N ) )  e.  RR )
242recnd 9008 . . . . . 6  |-  ( ph  ->  N  e.  CC )
25242halvesd 10106 . . . . 5  |-  ( ph  ->  ( ( N  / 
2 )  +  ( N  /  2 ) )  =  N )
267a1i 10 . . . . . . . . 9  |-  ( ph  ->  M  C_  ( 1 ... N ) )
2715peano2nnd 9910 . . . . . . . . . . . . 13  |-  ( ph  ->  ( K  +  1 )  e.  NN )
28 elfzuz 10947 . . . . . . . . . . . . 13  |-  ( k  e.  ( ( K  +  1 ) ... N )  ->  k  e.  ( ZZ>= `  ( K  +  1 ) ) )
29 nnuz 10414 . . . . . . . . . . . . . 14  |-  NN  =  ( ZZ>= `  1 )
3029uztrn2 10396 . . . . . . . . . . . . 13  |-  ( ( ( K  +  1 )  e.  NN  /\  k  e.  ( ZZ>= `  ( K  +  1
) ) )  -> 
k  e.  NN )
3127, 28, 30syl2an 463 . . . . . . . . . . . 12  |-  ( (
ph  /\  k  e.  ( ( K  + 
1 ) ... N
) )  ->  k  e.  NN )
32 eleq1 2426 . . . . . . . . . . . . . . . . 17  |-  ( p  =  k  ->  (
p  e.  Prime  <->  k  e.  Prime ) )
33 breq1 4128 . . . . . . . . . . . . . . . . 17  |-  ( p  =  k  ->  (
p  ||  n  <->  k  ||  n ) )
3432, 33anbi12d 691 . . . . . . . . . . . . . . . 16  |-  ( p  =  k  ->  (
( p  e.  Prime  /\  p  ||  n )  <-> 
( k  e.  Prime  /\  k  ||  n ) ) )
3534rabbidv 2865 . . . . . . . . . . . . . . 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 6006 . . . . . . . . . . . . . . . 16  |-  ( 1 ... N )  e. 
_V
3837rabex 4267 . . . . . . . . . . . . . . 15  |-  { n  e.  ( 1 ... N
)  |  ( k  e.  Prime  /\  k  ||  n ) }  e.  _V
3935, 36, 38fvmpt 5709 . . . . . . . . . . . . . 14  |-  ( k  e.  NN  ->  ( W `  k )  =  { n  e.  ( 1 ... N )  |  ( k  e. 
Prime  /\  k  ||  n
) } )
4039adantl 452 . . . . . . . . . . . . 13  |-  ( (
ph  /\  k  e.  NN )  ->  ( W `
 k )  =  { n  e.  ( 1 ... N )  |  ( k  e. 
Prime  /\  k  ||  n
) } )
41 ssrab2 3344 . . . . . . . . . . . . . 14  |-  { n  e.  ( 1 ... N
)  |  ( k  e.  Prime  /\  k  ||  n ) }  C_  ( 1 ... N
)
4241a1i 10 . . . . . . . . . . . . 13  |-  ( (
ph  /\  k  e.  NN )  ->  { n  e.  ( 1 ... N
)  |  ( k  e.  Prime  /\  k  ||  n ) }  C_  ( 1 ... N
) )
4340, 42eqsstrd 3298 . . . . . . . . . . . 12  |-  ( (
ph  /\  k  e.  NN )  ->  ( W `
 k )  C_  ( 1 ... N
) )
4431, 43syldan 456 . . . . . . . . . . 11  |-  ( (
ph  /\  k  e.  ( ( K  + 
1 ) ... N
) )  ->  ( W `  k )  C_  ( 1 ... N
) )
4544ralrimiva 2711 . . . . . . . . . 10  |-  ( ph  ->  A. k  e.  ( ( K  +  1 ) ... N ) ( W `  k
)  C_  ( 1 ... N ) )
46 iunss 4045 . . . . . . . . . 10  |-  ( U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) 
C_  ( 1 ... N )  <->  A. k  e.  ( ( K  + 
1 ) ... N
) ( W `  k )  C_  (
1 ... N ) )
4745, 46sylibr 203 . . . . . . . . 9  |-  ( ph  ->  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
)  C_  ( 1 ... N ) )
4826, 47unssd 3439 . . . . . . . 8  |-  ( ph  ->  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) )  C_  ( 1 ... N ) )
49 breq1 4128 . . . . . . . . . . . . . . . . . 18  |-  ( p  =  q  ->  (
p  ||  n  <->  q  ||  n ) )
5049notbid 285 . . . . . . . . . . . . . . . . 17  |-  ( p  =  q  ->  ( -.  p  ||  n  <->  -.  q  ||  n ) )
5150cbvralv 2849 . . . . . . . . . . . . . . . 16  |-  ( A. p  e.  ( Prime  \  ( 1 ... K
) )  -.  p  ||  n  <->  A. q  e.  ( Prime  \  ( 1 ... K ) )  -.  q  ||  n
)
52 breq2 4129 . . . . . . . . . . . . . . . . . 18  |-  ( n  =  x  ->  (
q  ||  n  <->  q  ||  x ) )
5352notbid 285 . . . . . . . . . . . . . . . . 17  |-  ( n  =  x  ->  ( -.  q  ||  n  <->  -.  q  ||  x ) )
5453ralbidv 2648 . . . . . . . . . . . . . . . 16  |-  ( n  =  x  ->  ( A. q  e.  ( Prime  \  ( 1 ... K ) )  -.  q  ||  n  <->  A. q  e.  ( Prime  \  (
1 ... K ) )  -.  q  ||  x
) )
5551, 54syl5bb 248 . . . . . . . . . . . . . . 15  |-  ( n  =  x  ->  ( A. p  e.  ( Prime  \  ( 1 ... K ) )  -.  p  ||  n  <->  A. q  e.  ( Prime  \  (
1 ... K ) )  -.  q  ||  x
) )
5655, 5elrab2 3011 . . . . . . . . . . . . . 14  |-  ( x  e.  M  <->  ( x  e.  ( 1 ... N
)  /\  A. q  e.  ( Prime  \  (
1 ... K ) )  -.  q  ||  x
) )
57 elun1 3430 . . . . . . . . . . . . . 14  |-  ( x  e.  M  ->  x  e.  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) ) )
5856, 57sylbir 204 . . . . . . . . . . . . 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 ) ) )
5958ex 423 . . . . . . . . . . . 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
) ) ) )
6059adantl 452 . . . . . . . . . . 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
) ) ) )
61 dfrex2 2641 . . . . . . . . . . . 12  |-  ( E. q  e.  ( Prime  \  ( 1 ... K ) ) q 
||  x  <->  -.  A. q  e.  ( Prime  \  (
1 ... K ) )  -.  q  ||  x
)
62 eldifn 3386 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( q  e.  ( Prime  \  (
1 ... K ) )  ->  -.  q  e.  ( 1 ... K
) )
6362ad2antrl 708 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  -.  q  e.  ( 1 ... K
) )
64 eldifi 3385 . . . . . . . . . . . . . . . . . . . . . . . . 25  |-  ( q  e.  ( Prime  \  (
1 ... K ) )  ->  q  e.  Prime )
6564ad2antrl 708 . . . . . . . . . . . . . . . . . . . . . . . 24  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  e.  Prime )
66 prmnn 12969 . . . . . . . . . . . . . . . . . . . . . . . 24  |-  ( q  e.  Prime  ->  q  e.  NN )
6765, 66syl 15 . . . . . . . . . . . . . . . . . . . . . . 23  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  e.  NN )
6867, 29syl6eleq 2456 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  e.  (
ZZ>= `  1 ) )
6915nnzd 10267 . . . . . . . . . . . . . . . . . . . . . . 23  |-  ( ph  ->  K  e.  ZZ )
7069ad2antrr 706 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  K  e.  ZZ )
71 elfz5 10943 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( ( q  e.  ( ZZ>= ` 
1 )  /\  K  e.  ZZ )  ->  (
q  e.  ( 1 ... K )  <->  q  <_  K ) )
7268, 70, 71syl2anc 642 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  ( q  e.  ( 1 ... K
)  <->  q  <_  K
) )
7363, 72mtbid 291 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  -.  q  <_  K )
7415nnred 9908 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( ph  ->  K  e.  RR )
7574ad2antrr 706 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  K  e.  RR )
7667nnred 9908 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  e.  RR )
7775, 76ltnled 9113 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  ( K  < 
q  <->  -.  q  <_  K ) )
7873, 77mpbird 223 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  K  <  q
)
79 prmz 12970 . . . . . . . . . . . . . . . . . . . . 21  |-  ( q  e.  Prime  ->  q  e.  ZZ )
8065, 79syl 15 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  e.  ZZ )
81 zltp1le 10218 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( K  e.  ZZ  /\  q  e.  ZZ )  ->  ( K  <  q  <->  ( K  +  1 )  <_  q ) )
8270, 80, 81syl2anc 642 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  ( K  < 
q  <->  ( K  + 
1 )  <_  q
) )
8378, 82mpbid 201 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  ( K  + 
1 )  <_  q
)
84 elfznn 10972 . . . . . . . . . . . . . . . . . . . . 21  |-  ( x  e.  ( 1 ... N )  ->  x  e.  NN )
8584ad2antlr 707 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  x  e.  NN )
8685nnred 9908 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  x  e.  RR )
872ad2antrr 706 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  N  e.  RR )
88 simprr 733 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  ||  x
)
89 dvdsle 12782 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( q  e.  ZZ  /\  x  e.  NN )  ->  ( q  ||  x  ->  q  <_  x )
)
9080, 85, 89syl2anc 642 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  ( q  ||  x  ->  q  <_  x
) )
9188, 90mpd 14 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  <_  x
)
92 elfzle2 10953 . . . . . . . . . . . . . . . . . . . 20  |-  ( x  e.  ( 1 ... N )  ->  x  <_  N )
9392ad2antlr 707 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  x  <_  N
)
9476, 86, 87, 91, 93letrd 9120 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  <_  N
)
9569peano2zd 10271 . . . . . . . . . . . . . . . . . . . 20  |-  ( ph  ->  ( K  +  1 )  e.  ZZ )
9695ad2antrr 706 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  ( K  + 
1 )  e.  ZZ )
971nnzd 10267 . . . . . . . . . . . . . . . . . . . 20  |-  ( ph  ->  N  e.  ZZ )
9897ad2antrr 706 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  N  e.  ZZ )
99 elfz 10941 . . . . . . . . . . . . . . . . . . 19  |-  ( ( q  e.  ZZ  /\  ( K  +  1
)  e.  ZZ  /\  N  e.  ZZ )  ->  ( q  e.  ( ( K  +  1 ) ... N )  <-> 
( ( K  + 
1 )  <_  q  /\  q  <_  N ) ) )
10080, 96, 98, 99syl3anc 1183 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  ( q  e.  ( ( K  + 
1 ) ... N
)  <->  ( ( K  +  1 )  <_ 
q  /\  q  <_  N ) ) )
10183, 94, 100mpbir2and 888 . . . . . . . . . . . . . . . . 17  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  e.  ( ( K  +  1 ) ... N ) )
102 simplr 731 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  x  e.  ( 1 ... N ) )
10365, 88jca 518 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  ( q  e. 
Prime  /\  q  ||  x
) )
10452anbi2d 684 . . . . . . . . . . . . . . . . . . . 20  |-  ( n  =  x  ->  (
( q  e.  Prime  /\  q  ||  n )  <-> 
( q  e.  Prime  /\  q  ||  x ) ) )
105104elrab 3009 . . . . . . . . . . . . . . . . . . 19  |-  ( x  e.  { n  e.  ( 1 ... N
)  |  ( q  e.  Prime  /\  q  ||  n ) }  <->  ( x  e.  ( 1 ... N
)  /\  ( q  e.  Prime  /\  q  ||  x ) ) )
106102, 103, 105sylanbrc 645 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  x  e.  {
n  e.  ( 1 ... N )  |  ( q  e.  Prime  /\  q  ||  n ) } )
107 eleq1 2426 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( p  =  q  ->  (
p  e.  Prime  <->  q  e.  Prime ) )
108107, 49anbi12d 691 . . . . . . . . . . . . . . . . . . . . 21  |-  ( p  =  q  ->  (
( p  e.  Prime  /\  p  ||  n )  <-> 
( q  e.  Prime  /\  q  ||  n ) ) )
109108rabbidv 2865 . . . . . . . . . . . . . . . . . . . 20  |-  ( p  =  q  ->  { n  e.  ( 1 ... N
)  |  ( p  e.  Prime  /\  p  ||  n ) }  =  { n  e.  (
1 ... N )  |  ( q  e.  Prime  /\  q  ||  n ) } )
11037rabex 4267 . . . . . . . . . . . . . . . . . . . 20  |-  { n  e.  ( 1 ... N
)  |  ( q  e.  Prime  /\  q  ||  n ) }  e.  _V
111109, 36, 110fvmpt 5709 . . . . . . . . . . . . . . . . . . 19  |-  ( q  e.  NN  ->  ( W `  q )  =  { n  e.  ( 1 ... N )  |  ( q  e. 
Prime  /\  q  ||  n
) } )
11267, 111syl 15 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  ( W `  q )  =  {
n  e.  ( 1 ... N )  |  ( q  e.  Prime  /\  q  ||  n ) } )
113106, 112eleqtrrd 2443 . . . . . . . . . . . . . . . . 17  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  x  e.  ( W `  q ) )
114 fveq2 5632 . . . . . . . . . . . . . . . . . . 19  |-  ( k  =  q  ->  ( W `  k )  =  ( W `  q ) )
115114eleq2d 2433 . . . . . . . . . . . . . . . . . 18  |-  ( k  =  q  ->  (
x  e.  ( W `
 k )  <->  x  e.  ( W `  q ) ) )
116115rspcev 2969 . . . . . . . . . . . . . . . . 17  |-  ( ( q  e.  ( ( K  +  1 ) ... N )  /\  x  e.  ( W `  q ) )  ->  E. k  e.  (
( K  +  1 ) ... N ) x  e.  ( W `
 k ) )
117101, 113, 116syl2anc 642 . . . . . . . . . . . . . . . 16  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  E. k  e.  ( ( K  +  1 ) ... N ) x  e.  ( W `
 k ) )
118 eliun 4011 . . . . . . . . . . . . . . . 16  |-  ( x  e.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k )  <->  E. k  e.  ( ( K  + 
1 ) ... N
) x  e.  ( W `  k ) )
119117, 118sylibr 203 . . . . . . . . . . . . . . 15  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  x  e.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) )
120 elun2 3431 . . . . . . . . . . . . . . 15  |-  ( x  e.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k )  ->  x  e.  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) ) )
121119, 120syl 15 . . . . . . . . . . . . . 14  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  x  e.  ( M  u.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) )
122121expr 598 . . . . . . . . . . . . 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 ) ) ) )
123122rexlimdva 2752 . . . . . . . . . . . 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 ) ) ) )
12461, 123syl5bir 209 . . . . . . . . . . 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 ) ) ) )
12560, 124pm2.61d 150 . . . . . . . . . 10  |-  ( (
ph  /\  x  e.  ( 1 ... N
) )  ->  x  e.  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) ) )
126125ex 423 . . . . . . . . 9  |-  ( ph  ->  ( x  e.  ( 1 ... N )  ->  x  e.  ( M  u.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) ) )
127126ssrdv 3271 . . . . . . . 8  |-  ( ph  ->  ( 1 ... N
)  C_  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) ) )
12848, 127eqssd 3282 . . . . . . 7  |-  ( ph  ->  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) )  =  ( 1 ... N ) )
129128fveq2d 5636 . . . . . 6  |-  ( ph  ->  ( # `  ( M  u.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) )  =  ( # `  (
1 ... N ) ) )
1301nnnn0d 10167 . . . . . . 7  |-  ( ph  ->  N  e.  NN0 )
131 hashfz1 11517 . . . . . . 7  |-  ( N  e.  NN0  ->  ( # `  ( 1 ... N
) )  =  N )
132130, 131syl 15 . . . . . 6  |-  ( ph  ->  ( # `  (
1 ... N ) )  =  N )
133129, 132eqtr2d 2399 . . . . 5  |-  ( ph  ->  N  =  ( # `  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) ) ) )
1349a1i 10 . . . . . 6  |-  ( ph  ->  M  e.  Fin )
135 ssfi 7226 . . . . . . 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 )
1364, 47, 135sylancr 644 . . . . . 6  |-  ( ph  ->  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
)  e.  Fin )
137 simprr 733 . . . . . . . . . . . . . . . . 17  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  k  e.  Prime )
138 noel 3547 . . . . . . . . . . . . . . . . . 18  |-  -.  k  e.  (/)
139 simprl 732 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  k  e.  ( ( K  +  1 ) ... N ) )
140139biantrud 493 . . . . . . . . . . . . . . . . . . . 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
) ) ) )
141 elin 3446 . . . . . . . . . . . . . . . . . . . 20  |-  ( k  e.  ( ( 1 ... K )  i^i  ( ( K  + 
1 ) ... N
) )  <->  ( k  e.  ( 1 ... K
)  /\  k  e.  ( ( K  + 
1 ) ... N
) ) )
142140, 141syl6bbr 254 . . . . . . . . . . . . . . . . . . 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 ) ) ) )
14374ltp1d 9834 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( ph  ->  K  <  ( K  +  1 ) )
144 fzdisj 10970 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( K  <  ( K  + 
1 )  ->  (
( 1 ... K
)  i^i  ( ( K  +  1 ) ... N ) )  =  (/) )
145143, 144syl 15 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ph  ->  ( ( 1 ... K )  i^i  (
( K  +  1 ) ... N ) )  =  (/) )
146145ad2antrr 706 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  ( ( 1 ... K )  i^i  ( ( K  + 
1 ) ... N
) )  =  (/) )
147146eleq2d 2433 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  ( k  e.  ( ( 1 ... K )  i^i  (
( K  +  1 ) ... N ) )  <->  k  e.  (/) ) )
148142, 147bitrd 244 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  ( k  e.  ( 1 ... K
)  <->  k  e.  (/) ) )
149138, 148mtbiri 294 . . . . . . . . . . . . . . . . 17  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  -.  k  e.  ( 1 ... K
) )
150 eldif 3248 . . . . . . . . . . . . . . . . 17  |-  ( k  e.  ( Prime  \  (
1 ... K ) )  <-> 
( k  e.  Prime  /\ 
-.  k  e.  ( 1 ... K ) ) )
151137, 149, 150sylanbrc 645 . . . . . . . . . . . . . . . 16  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  k  e.  ( Prime  \  ( 1 ... K ) ) )
152 breq2 4129 . . . . . . . . . . . . . . . . . . . . 21  |-  ( n  =  x  ->  (
p  ||  n  <->  p  ||  x
) )
153152notbid 285 . . . . . . . . . . . . . . . . . . . 20  |-  ( n  =  x  ->  ( -.  p  ||  n  <->  -.  p  ||  x ) )
154153ralbidv 2648 . . . . . . . . . . . . . . . . . . 19  |-  ( n  =  x  ->  ( A. p  e.  ( Prime  \  ( 1 ... K ) )  -.  p  ||  n  <->  A. p  e.  ( Prime  \  (
1 ... K ) )  -.  p  ||  x
) )
155154, 5elrab2 3011 . . . . . . . . . . . . . . . . . 18  |-  ( x  e.  M  <->  ( x  e.  ( 1 ... N
)  /\  A. p  e.  ( Prime  \  (
1 ... K ) )  -.  p  ||  x
) )
156155simprbi 450 . . . . . . . . . . . . . . . . 17  |-  ( x  e.  M  ->  A. p  e.  ( Prime  \  (
1 ... K ) )  -.  p  ||  x
)
157156ad2antlr 707 . . . . . . . . . . . . . . . 16  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  A. p  e.  ( Prime  \  ( 1 ... K ) )  -.  p  ||  x
)
158 breq1 4128 . . . . . . . . . . . . . . . . . 18  |-  ( p  =  k  ->  (
p  ||  x  <->  k  ||  x ) )
159158notbid 285 . . . . . . . . . . . . . . . . 17  |-  ( p  =  k  ->  ( -.  p  ||  x  <->  -.  k  ||  x ) )
160159rspcv 2965 . . . . . . . . . . . . . . . 16  |-  ( k  e.  ( Prime  \  (
1 ... K ) )  ->  ( A. p  e.  ( Prime  \  (
1 ... K ) )  -.  p  ||  x  ->  -.  k  ||  x
) )
161151, 157, 160sylc 56 . . . . . . . . . . . . . . 15  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  -.  k  ||  x )
162161expr 598 . . . . . . . . . . . . . 14  |-  ( ( ( ph  /\  x  e.  M )  /\  k  e.  ( ( K  + 
1 ) ... N
) )  ->  (
k  e.  Prime  ->  -.  k  ||  x ) )
163 imnan 411 . . . . . . . . . . . . . 14  |-  ( ( k  e.  Prime  ->  -.  k  ||  x )  <->  -.  ( k  e.  Prime  /\  k  ||  x ) )
164162, 163sylib 188 . . . . . . . . . . . . 13  |-  ( ( ( ph  /\  x  e.  M )  /\  k  e.  ( ( K  + 
1 ) ... N
) )  ->  -.  ( k  e.  Prime  /\  k  ||  x ) )
16531adantlr 695 . . . . . . . . . . . . . . . 16  |-  ( ( ( ph  /\  x  e.  M )  /\  k  e.  ( ( K  + 
1 ) ... N
) )  ->  k  e.  NN )
166165, 39syl 15 . . . . . . . . . . . . . . 15  |-  ( ( ( ph  /\  x  e.  M )  /\  k  e.  ( ( K  + 
1 ) ... N
) )  ->  ( W `  k )  =  { n  e.  ( 1 ... N )  |  ( k  e. 
Prime  /\  k  ||  n
) } )
167166eleq2d 2433 . . . . . . . . . . . . . 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 ) } ) )
168 breq2 4129 . . . . . . . . . . . . . . . . 17  |-  ( n  =  x  ->  (
k  ||  n  <->  k  ||  x ) )
169168anbi2d 684 . . . . . . . . . . . . . . . 16  |-  ( n  =  x  ->  (
( k  e.  Prime  /\  k  ||  n )  <-> 
( k  e.  Prime  /\  k  ||  x ) ) )
170169elrab 3009 . . . . . . . . . . . . . . 15  |-  ( x  e.  { n  e.  ( 1 ... N
)  |  ( k  e.  Prime  /\  k  ||  n ) }  <->  ( x  e.  ( 1 ... N
)  /\  ( k  e.  Prime  /\  k  ||  x ) ) )
171170simprbi 450 . . . . . . . . . . . . . 14  |-  ( x  e.  { n  e.  ( 1 ... N
)  |  ( k  e.  Prime  /\  k  ||  n ) }  ->  ( k  e.  Prime  /\  k  ||  x ) )
172167, 171syl6bi 219 . . . . . . . . . . . . 13  |-  ( ( ( ph  /\  x  e.  M )  /\  k  e.  ( ( K  + 
1 ) ... N
) )  ->  (
x  e.  ( W `
 k )  -> 
( k  e.  Prime  /\  k  ||  x ) ) )
173164, 172mtod 168 . . . . . . . . . . . 12  |-  ( ( ( ph  /\  x  e.  M )  /\  k  e.  ( ( K  + 
1 ) ... N
) )  ->  -.  x  e.  ( W `  k ) )
174173nrexdv 2731 . . . . . . . . . . 11  |-  ( (
ph  /\  x  e.  M )  ->  -.  E. k  e.  ( ( K  +  1 ) ... N ) x  e.  ( W `  k ) )
175174, 118sylnibr 296 . . . . . . . . . 10  |-  ( (
ph  /\  x  e.  M )  ->  -.  x  e.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) )
176175ex 423 . . . . . . . . 9  |-  ( ph  ->  ( x  e.  M  ->  -.  x  e.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) ) )
177 imnan 411 . . . . . . . . 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 ) ) )
178176, 177sylib 188 . . . . . . . 8  |-  ( ph  ->  -.  ( x  e.  M  /\  x  e. 
U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) ) )
179 elin 3446 . . . . . . . 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
) ) )
180178, 179sylnibr 296 . . . . . . 7  |-  ( ph  ->  -.  x  e.  ( M  i^i  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) )
181180eq0rdv 3577 . . . . . 6  |-  ( ph  ->  ( M  i^i  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) )  =  (/) )
182 hashun 11543 . . . . . 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 ) ) ) )
183134, 136, 181, 182syl3anc 1183 . . . . 5  |-  ( ph  ->  ( # `  ( M  u.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) )  =  ( ( # `  M )  +  (
# `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) ) )
18425, 133, 1833eqtrd 2402 . . . 4  |-  ( ph  ->  ( ( N  / 
2 )  +  ( N  /  2 ) )  =  ( (
# `  M )  +  ( # `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) ) )
185 hashcl 11526 . . . . . . 7  |-  ( U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k )  e.  Fin  ->  ( # `
 U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) )  e.  NN0 )
186136, 185syl 15 . . . . . 6  |-  ( ph  ->  ( # `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) )  e. 
NN0 )
187186nn0red 10168 . . . . 5  |-  ( ph  ->  ( # `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) )  e.  RR )
188 fzfid 11199 . . . . . . . 8  |-  ( ph  ->  ( ( K  + 
1 ) ... N
)  e.  Fin )
18927, 30sylan 457 . . . . . . . . . 10  |-  ( (
ph  /\  k  e.  ( ZZ>= `  ( K  +  1 ) ) )  ->  k  e.  NN )
190 nnrecre 9929 . . . . . . . . . . 11  |-  ( k  e.  NN  ->  (
1  /  k )  e.  RR )
191 0re 8985 . . . . . . . . . . 11  |-  0  e.  RR
192 ifcl 3690 . . . . . . . . . . 11  |-  ( ( ( 1  /  k
)  e.  RR  /\  0  e.  RR )  ->  if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 )  e.  RR )
193190, 191, 192sylancl 643 . . . . . . . . . 10  |-  ( k  e.  NN  ->  if ( k  e.  Prime ,  ( 1  /  k
) ,  0 )  e.  RR )
194189, 193syl 15 . . . . . . . . 9  |-  ( (
ph  /\  k  e.  ( ZZ>= `  ( K  +  1 ) ) )  ->  if (
k  e.  Prime ,  ( 1  /  k ) ,  0 )  e.  RR )
19528, 194sylan2 460 . . . . . . . 8  |-  ( (
ph  /\  k  e.  ( ( K  + 
1 ) ... N
) )  ->  if ( k  e.  Prime ,  ( 1  /  k
) ,  0 )  e.  RR )
196188, 195fsumrecl 12415 . . . . . . 7  |-  ( ph  -> 
sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 )  e.  RR )
1972, 196remulcld 9010 . . . . . 6  |-  ( ph  ->  ( N  x.  sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) )  e.  RR )
198 prmrec.1 . . . . . . . 8  |-  F  =  ( n  e.  NN  |->  if ( n  e.  Prime ,  ( 1  /  n
) ,  0 ) )
199 prmrec.5 . . . . . . . 8  |-  ( ph  ->  seq  1 (  +  ,  F )  e. 
dom 
~~>  )
200 prmrec.6 . . . . . . . 8  |-  ( ph  -> 
sum_ k  e.  (
ZZ>= `  ( K  + 
1 ) ) if ( k  e.  Prime ,  ( 1  /  k
) ,  0 )  <  ( 1  / 
2 ) )
201198, 15, 1, 5, 199, 200, 36prmreclem4 13174 . . . . . . 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 ) ) ) )
202 eluz 10392 . . . . . . . . . 10  |-  ( ( N  e.  ZZ  /\  K  e.  ZZ )  ->  ( K  e.  (
ZZ>= `  N )  <->  N  <_  K ) )
20397, 69, 202syl2anc 642 . . . . . . . . 9  |-  ( ph  ->  ( K  e.  (
ZZ>= `  N )  <->  N  <_  K ) )
204 nnleltp1 10222 . . . . . . . . . 10  |-  ( ( N  e.  NN  /\  K  e.  NN )  ->  ( N  <_  K  <->  N  <  ( K  + 
1 ) ) )
2051, 15, 204syl2anc 642 . . . . . . . . 9  |-  ( ph  ->  ( N  <_  K  <->  N  <  ( K  + 
1 ) ) )
206 fzn 10963 . . . . . . . . . 10  |-  ( ( ( K  +  1 )  e.  ZZ  /\  N  e.  ZZ )  ->  ( N  <  ( K  +  1 )  <-> 
( ( K  + 
1 ) ... N
)  =  (/) ) )
20795, 97, 206syl2anc 642 . . . . . . . . 9  |-  ( ph  ->  ( N  <  ( K  +  1 )  <-> 
( ( K  + 
1 ) ... N
)  =  (/) ) )
208203, 205, 2073bitrd 270 . . . . . . . 8  |-  ( ph  ->  ( K  e.  (
ZZ>= `  N )  <->  ( ( K  +  1 ) ... N )  =  (/) ) )
209 0le0 9974 . . . . . . . . . 10  |-  0  <_  0
21024mul01d 9158 . . . . . . . . . 10  |-  ( ph  ->  ( N  x.  0 )  =  0 )
211209, 210syl5breqr 4161 . . . . . . . . 9  |-  ( ph  ->  0  <_  ( N  x.  0 ) )
212 iuneq1 4020 . . . . . . . . . . . . 13  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k )  =  U_ k  e.  (/)  ( W `
 k ) )
213 0iun 4061 . . . . . . . . . . . . 13  |-  U_ k  e.  (/)  ( W `  k )  =  (/)
214212, 213syl6eq 2414 . . . . . . . . . . . 12  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k )  =  (/) )
215214fveq2d 5636 . . . . . . . . . . 11  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  ( # `  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) )  =  (
# `  (/) ) )
216 hash0 11533 . . . . . . . . . . 11  |-  ( # `  (/) )  =  0
217215, 216syl6eq 2414 . . . . . . . . . 10  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  ( # `  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) )  =  0 )
218 sumeq1 12370 . . . . . . . . . . . 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 ) )
219 sum0 12402 . . . . . . . . . . . 12  |-  sum_ k  e.  (/)  if ( k  e.  Prime ,  ( 1  /  k ) ,  0 )  =  0
220218, 219syl6eq 2414 . . . . . . . . . . 11  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  sum_ k  e.  ( ( K  + 
1 ) ... N
) if ( k  e.  Prime ,  ( 1  /  k ) ,  0 )  =  0 )
221220oveq2d 5997 . . . . . . . . . 10  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  ( N  x.  sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 ) )  =  ( N  x.  0 ) )
222217, 221breq12d 4138 . . . . . . . . 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 ) ) )
223211, 222syl5ibrcom 213 . . . . . . . 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 ) ) ) )
224208, 223sylbid 206 . . . . . . 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 ) ) ) )
225 uztric 10400 . . . . . . . 8  |-  ( ( K  e.  ZZ  /\  N  e.  ZZ )  ->  ( N  e.  (
ZZ>= `  K )  \/  K  e.  ( ZZ>= `  N ) ) )
22669, 97, 225syl2anc 642 . . . . . . 7  |-  ( ph  ->  ( N  e.  (
ZZ>= `  K )  \/  K  e.  ( ZZ>= `  N ) ) )
227201, 224, 226mpjaod 370 . . . . . 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 ) ) )
228 eqid 2366 . . . . . . . . . 10  |-  ( ZZ>= `  ( K  +  1
) )  =  (
ZZ>= `  ( K  + 
1 ) )
229 eleq1 2426 . . . . . . . . . . . . 13  |-  ( n  =  k  ->  (
n  e.  Prime  <->  k  e.  Prime ) )
230 oveq2 5989 . . . . . . . . . . . . 13  |-  ( n  =  k  ->  (
1  /  n )  =  ( 1  / 
k ) )
231 eqidd 2367 . . . . . . . . . . . . 13  |-  ( n  =  k  ->  0  =  0 )
232229, 230, 231ifbieq12d 3676 . . . . . . . . . . . 12  |-  ( n  =  k  ->  if ( n  e.  Prime ,  ( 1  /  n
) ,  0 )  =  if ( k  e.  Prime ,  ( 1  /  k ) ,  0 ) )
233 ovex 6006 . . . . . . . . . . . . 13  |-  ( 1  /  k )  e. 
_V
234 c0ex 8979 . . . . . . . . . . . . 13  |-  0  e.  _V
235233, 234ifex 3712 . . . . . . . . . . . 12  |-  if ( k  e.  Prime ,  ( 1  /  k ) ,  0 )  e. 
_V
236232, 198, 235fvmpt 5709 . . . . . . . . . . 11  |-  ( k  e.  NN  ->  ( F `  k )  =  if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 ) )
237189, 236syl 15 . . . . . . . . . 10  |-  ( (
ph  /\  k  e.  ( ZZ>= `  ( K  +  1 ) ) )  ->  ( F `  k )  =  if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) )
238193recnd 9008 . . . . . . . . . . . . . 14  |-  ( k  e.  NN  ->  if ( k  e.  Prime ,  ( 1  /  k
) ,  0 )  e.  CC )
239236, 238eqeltrd 2440 . . . . . . . . . . . . 13  |-  ( k  e.  NN  ->  ( F `  k )  e.  CC )
240239adantl 452 . . . . . . . . . . . 12  |-  ( (
ph  /\  k  e.  NN )  ->  ( F `
 k )  e.  CC )
24129, 27, 240iserex 12337 . . . . . . . . . . 11  |-  ( ph  ->  (  seq  1 (  +  ,  F )  e.  dom  ~~>  <->  seq  ( K  +  1 ) (  +  ,  F )  e.  dom  ~~>  ) )
242199, 241mpbid 201 . . . . . . . . . 10  |-  ( ph  ->  seq  ( K  + 
1 ) (  +  ,  F )  e. 
dom 
~~>  )
243228, 95, 237, 194, 242isumrecl 12436 . . . . . . . . 9  |-  ( ph  -> 
sum_ k  e.  (
ZZ>= `  ( K  + 
1 ) ) if ( k  e.  Prime ,  ( 1  /  k
) ,  0 )  e.  RR )
244 1re 8984 . . . . . . . . . . 11  |-  1  e.  RR
245 rehalfcl 10087 . . . . . . . . . . 11  |-  ( 1  e.  RR  ->  (
1  /  2 )  e.  RR )
246244, 245ax-mp 8 . . . . . . . . . 10  |-  ( 1  /  2 )  e.  RR
247246a1i 10 . . . . . . . . 9  |-  ( ph  ->  ( 1  /  2
)  e.  RR )
248 fzssuz 10985 . . . . . . . . . . 11  |-  ( ( K  +  1 ) ... N )  C_  ( ZZ>= `  ( K  +  1 ) )
249248a1i 10 . . . . . . . . . 10  |-  ( ph  ->  ( ( K  + 
1 ) ... N
)  C_  ( ZZ>= `  ( K  +  1
) ) )
250 nnrp 10514 . . . . . . . . . . . . . 14  |-  ( k  e.  NN  ->  k  e.  RR+ )
251250rpreccld 10551 . . . . . . . . . . . . 13  |-  ( k  e.  NN  ->  (
1  /  k )  e.  RR+ )
252251rpge0d 10545 . . . . . . . . . . . 12  |-  ( k  e.  NN  ->  0  <_  ( 1  /  k
) )
253 breq2 4129 . . . . . . . . . . . . 13  |-  ( ( 1  /  k )  =  if ( k  e.  Prime ,  ( 1  /  k ) ,  0 )  ->  (
0  <_  ( 1  /  k )  <->  0  <_  if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) ) )
254 breq2 4129 . . . . . . . . . . . . 13  |-  ( 0  =  if ( k  e.  Prime ,  ( 1  /  k ) ,  0 )  ->  (
0  <_  0  <->  0  <_  if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) ) )
255253, 254ifboth 3685 . . . . . . . . . . . 12  |-  ( ( 0  <_  ( 1  /  k )  /\  0  <_  0 )  -> 
0  <_  if (
k  e.  Prime ,  ( 1  /  k ) ,  0 ) )
256252, 209, 255sylancl 643 . . . . . . . . . . 11  |-  ( k  e.  NN  ->  0  <_  if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 ) )
257189, 256syl 15 . . . . . . . . . 10  |-  ( (
ph  /\  k  e.  ( ZZ>= `  ( K  +  1 ) ) )  ->  0  <_  if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) )
258228, 95, 188, 249, 237, 194, 257, 242isumless 12512 . . . . . . . . 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 ) )
259196, 243, 247, 258, 200lelttrd 9121 . . . . . . . 8  |-  ( ph  -> 
sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 )  <  (
1  /  2 ) )
2601nngt0d 9936 . . . . . . . . 9  |-  ( ph  ->  0  <  N )
261 ltmul2 9754 . . . . . . . . 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 ) ) ) )
262196, 247, 2, 260, 261syl112anc 1187 . . . . . . . 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 ) ) ) )
263259, 262mpbid 201 . . . . . . 7  |-  ( ph  ->  ( N  x.  sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) )  <  ( N  x.  ( 1  / 
2 ) ) )
264 2cn 9963 . . . . . . . . 9  |-  2  e.  CC
265 2ne0 9976 . . . . . . . . 9  |-  2  =/=  0
266 divrec 9587 . . . . . . . . 9  |-  ( ( N  e.  CC  /\  2  e.  CC  /\  2  =/=  0 )  ->  ( N  /  2 )  =  ( N  x.  (
1  /  2 ) ) )
267264, 265, 266mp3an23 1270 . . . . . . . 8  |-  ( N  e.  CC  ->  ( N  /  2 )  =  ( N  x.  (
1  /  2 ) ) )
26824, 267syl 15 . . . . . . 7  |-  ( ph  ->  ( N  /  2
)  =  ( N  x.  ( 1  / 
2 ) ) )
269263, 268breqtrrd 4151 . . . . . 6  |-  ( ph  ->  ( N  x.  sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) )  <  ( N  /  2 ) )
270187, 197, 3, 227, 269lelttrd 9121 . . . . 5  |-  ( ph  ->  ( # `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) )  < 
( N  /  2
) )
271187, 3, 13, 270ltadd2dd 9122 . . . 4  |-  ( ph  ->  ( ( # `  M
)  +  ( # `  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) ) )  < 
( ( # `  M
)  +  ( N  /  2 ) ) )
272184, 271eqbrtrd 4145 . . 3  |-  ( ph  ->  ( ( N  / 
2 )  +  ( N  /  2 ) )  <  ( (
# `  M )  +  ( N  / 
2 ) ) )
2733, 13, 3ltadd1d 9512 . . 3  |-  ( ph  ->  ( ( N  / 
2 )  <  ( # `
 M )  <->  ( ( N  /  2 )  +  ( N  /  2
) )  <  (
( # `  M )  +  ( N  / 
2 ) ) ) )
274272, 273mpbird 223 . 2  |-  ( ph  ->  ( N  /  2
)  <  ( # `  M
) )
275 oveq1 5988 . . . . . . . 8  |-  ( k  =  r  ->  (
k ^ 2 )  =  ( r ^
2 ) )
276275breq1d 4135 . . . . . . 7  |-  ( k  =  r  ->  (
( k ^ 2 )  ||  x  <->  ( r ^ 2 )  ||  x ) )
277276cbvrabv 2872 . . . . . 6  |-  { k  e.  NN  |  ( k ^ 2 ) 
||  x }  =  { r  e.  NN  |  ( r ^
2 )  ||  x }
278 breq2 4129 . . . . . . 7  |-  ( x  =  n  ->  (
( r ^ 2 )  ||  x  <->  ( r ^ 2 )  ||  n ) )
279278rabbidv 2865 . . . . . 6  |-  ( x  =  n  ->  { r  e.  NN  |  ( r ^ 2 ) 
||  x }  =  { r  e.  NN  |  ( r ^
2 )  ||  n } )
280277, 279syl5eq 2410 . . . . 5  |-  ( x  =  n  ->  { k  e.  NN  |  ( k ^ 2 ) 
||  x }  =  { r  e.  NN  |  ( r ^
2 )  ||  n } )
281280supeq1d 7346 . . . 4  |-  ( x  =  n  ->  sup ( { k  e.  NN  |  ( k ^
2 )  ||  x } ,  RR ,  <  )  =  sup ( { r  e.  NN  |  ( r ^
2 )  ||  n } ,  RR ,  <  ) )
282281cbvmptv 4213 . . 3  |-  ( x  e.  NN  |->  sup ( { k  e.  NN  |  ( k ^
2 )  ||  x } ,  RR ,  <  ) )  =  ( n  e.  NN  |->  sup ( { r  e.  NN  |  ( r ^ 2 )  ||  n } ,  RR ,  <  ) )
283198, 15, 1, 5, 282prmreclem3 13173 . 2  |-  ( ph  ->  ( # `  M
)  <_  ( (
2 ^ K )  x.  ( sqr `  N
) ) )
2843, 13, 23, 274, 283ltletrd 9123 1  |-  ( ph  ->  ( N  /  2
)  <  ( (
2 ^ K )  x.  ( sqr `  N
) ) )
Colors of variables: wff set class
Syntax hints:   -. wn 3    -> wi 4    <-> wb 176    \/ wo 357    /\ wa 358    = wceq 1647    e. wcel 1715    =/= wne 2529   A.wral 2628   E.wrex 2629   {crab 2632    \ cdif 3235    u. cun 3236    i^i cin 3237    C_ wss 3238   (/)c0 3543   ifcif 3654   U_ciun 4007   class class class wbr 4125    e. cmpt 4179   dom cdm 4792   ` cfv 5358  (class class class)co 5981   Fincfn 7006   supcsup 7340   CCcc 8882   RRcr 8883   0cc0 8884   1c1 8885    + caddc 8887    x. cmul 8889    < clt 9014    <_ cle 9015    / cdiv 9570   NNcn 9893   2c2 9942   NN0cn0 10114   ZZcz 10175   ZZ>=cuz 10381   ...cfz 10935    seq cseq 11210   ^cexp 11269   #chash 11505   sqrcsqr 11925    ~~> cli 12165   sum_csu 12366    || cdivides 12739   Primecprime 12966
This theorem is referenced by:  prmreclem6  13176
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1551  ax-5 1562  ax-17 1621  ax-9 1659  ax-8 1680  ax-13 1717  ax-14 1719  ax-6 1734  ax-7 1739  ax-11 1751  ax-12 1937  ax-ext 2347  ax-rep 4233  ax-sep 4243  ax-nul 4251  ax-pow 4290  ax-pr 4316  ax-un 4615  ax-inf2 7489  ax-cnex 8940  ax-resscn 8941  ax-1cn 8942  ax-icn 8943  ax-addcl 8944  ax-addrcl 8945  ax-mulcl 8946  ax-mulrcl 8947  ax-mulcom 8948  ax-addass 8949  ax-mulass 8950  ax-distr 8951  ax-i2m1 8952  ax-1ne0 8953  ax-1rid 8954  ax-rnegex 8955  ax-rrecex 8956  ax-cnre 8957  ax-pre-lttri 8958  ax-pre-lttrn 8959  ax-pre-ltadd 8960  ax-pre-mulgt0 8961  ax-pre-sup 8962
This theorem depends on definitions:  df-bi 177  df-or 359  df-an 360  df-3or 936  df-3an 937  df-tru 1324  df-ex 1547  df-nf 1550  df-sb 1654  df-eu 2221  df-mo 2222  df-clab 2353  df-cleq 2359  df-clel 2362  df-nfc 2491  df-ne 2531  df-nel 2532  df-ral 2633  df-rex 2634  df-reu 2635  df-rmo 2636  df-rab 2637  df-v 2875  df-sbc 3078  df-csb 3168  df-dif 3241  df-un 3243  df-in 3245  df-ss 3252  df-pss 3254  df-nul 3544  df-if 3655  df-pw 3716  df-sn 3735  df-pr 3736  df-tp 3737  df-op 3738  df-uni 3930  df-int 3965  df-iun 4009  df-br 4126  df-opab 4180  df-mpt 4181  df-tr 4216  df-eprel 4408  df-id 4412  df-po 4417  df-so 4418  df-fr 4455  df-se 4456  df-we 4457  df-ord 4498  df-on 4499  df-lim 4500  df-suc 4501  df-om 4760  df-xp 4798  df-rel 4799  df-cnv 4800  df-co 4801  df-dm 4802  df-rn 4803  df-res 4804  df-ima 4805  df-iota 5322  df-fun 5360  df-fn 5361  df-f 5362  df-f1 5363  df-fo 5364  df-f1o 5365  df-fv 5366  df-isom 5367  df-ov 5984  df-oprab 5985  df-mpt2 5986  df-1st 6249  df-2nd 6250  df-riota 6446  df-recs 6530  df-rdg 6565  df-1o 6621  df-2o 6622  df-oadd 6625  df-er 6802  df-map 6917  df-pm 6918  df-en 7007  df-dom 7008  df-sdom 7009  df-fin 7010  df-sup 7341  df-oi 7372  df-card 7719  df-cda 7941  df-pnf 9016  df-mnf 9017  df-xr 9018  df-ltxr 9019  df-le 9020  df-sub 9186  df-neg 9187  df-div 9571  df-nn 9894  df-2 9951  df-3 9952  df-n0 10115  df-z 10176  df-uz 10382  df-q 10468  df-rp 10506  df-fz 10936  df-fzo 11026  df-fl 11089  df-mod 11138  df-seq 11211  df-exp 11270  df-hash 11506  df-cj 11791  df-re 11792  df-im 11793  df-sqr 11927  df-abs 11928  df-clim 12169  df-rlim 12170  df-sum 12367  df-dvds 12740  df-gcd 12894  df-prm 12967  df-pc 13098
  Copyright terms: Public domain W3C validator