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

Theorem prmreclem5 12967
Description: Lemma for prmrec 12969. 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 12966 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 9761 . . 3  |-  ( ph  ->  N  e.  RR )
32rehalfcld 9958 . 2  |-  ( ph  ->  ( N  /  2
)  e.  RR )
4 fzfi 11034 . . . . . 6  |-  ( 1 ... N )  e. 
Fin
5 prmrec.4 . . . . . . 7  |-  M  =  { n  e.  ( 1 ... N )  |  A. p  e.  ( Prime  \  (
1 ... K ) )  -.  p  ||  n }
6 ssrab2 3258 . . . . . . 7  |-  { n  e.  ( 1 ... N
)  |  A. p  e.  ( Prime  \  (
1 ... K ) )  -.  p  ||  n }  C_  ( 1 ... N )
75, 6eqsstri 3208 . . . . . 6  |-  M  C_  ( 1 ... N
)
8 ssfi 7083 . . . . . 6  |-  ( ( ( 1 ... N
)  e.  Fin  /\  M  C_  ( 1 ... N ) )  ->  M  e.  Fin )
94, 7, 8mp2an 653 . . . . 5  |-  M  e. 
Fin
10 hashcl 11350 . . . . 5  |-  ( M  e.  Fin  ->  ( # `
 M )  e. 
NN0 )
119, 10ax-mp 8 . . . 4  |-  ( # `  M )  e.  NN0
1211nn0rei 9976 . . 3  |-  ( # `  M )  e.  RR
1312a1i 10 . 2  |-  ( ph  ->  ( # `  M
)  e.  RR )
14 2nn 9877 . . . . 5  |-  2  e.  NN
15 prmrec.2 . . . . . 6  |-  ( ph  ->  K  e.  NN )
1615nnnn0d 10018 . . . . 5  |-  ( ph  ->  K  e.  NN0 )
17 nnexpcl 11116 . . . . 5  |-  ( ( 2  e.  NN  /\  K  e.  NN0 )  -> 
( 2 ^ K
)  e.  NN )
1814, 16, 17sylancr 644 . . . 4  |-  ( ph  ->  ( 2 ^ K
)  e.  NN )
1918nnred 9761 . . 3  |-  ( ph  ->  ( 2 ^ K
)  e.  RR )
201nnrpd 10389 . . . . 5  |-  ( ph  ->  N  e.  RR+ )
2120rpsqrcld 11894 . . . 4  |-  ( ph  ->  ( sqr `  N
)  e.  RR+ )
2221rpred 10390 . . 3  |-  ( ph  ->  ( sqr `  N
)  e.  RR )
2319, 22remulcld 8863 . 2  |-  ( ph  ->  ( ( 2 ^ K )  x.  ( sqr `  N ) )  e.  RR )
242recnd 8861 . . . . . 6  |-  ( ph  ->  N  e.  CC )
25242halvesd 9957 . . . . 5  |-  ( ph  ->  ( ( N  / 
2 )  +  ( N  /  2 ) )  =  N )
267a1i 10 . . . . . . . . 9  |-  ( ph  ->  M  C_  ( 1 ... N ) )
2715peano2nnd 9763 . . . . . . . . . . . . 13  |-  ( ph  ->  ( K  +  1 )  e.  NN )
28 elfzuz 10794 . . . . . . . . . . . . 13  |-  ( k  e.  ( ( K  +  1 ) ... N )  ->  k  e.  ( ZZ>= `  ( K  +  1 ) ) )
29 nnuz 10263 . . . . . . . . . . . . . 14  |-  NN  =  ( ZZ>= `  1 )
3029uztrn2 10245 . . . . . . . . . . . . 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 2343 . . . . . . . . . . . . . . . . 17  |-  ( p  =  k  ->  (
p  e.  Prime  <->  k  e.  Prime ) )
33 breq1 4026 . . . . . . . . . . . . . . . . 17  |-  ( p  =  k  ->  (
p  ||  n  <->  k  ||  n ) )
3432, 33anbi12d 691 . . . . . . . . . . . . . . . 16  |-  ( p  =  k  ->  (
( p  e.  Prime  /\  p  ||  n )  <-> 
( k  e.  Prime  /\  k  ||  n ) ) )
3534rabbidv 2780 . . . . . . . . . . . . . . 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 5883 . . . . . . . . . . . . . . . 16  |-  ( 1 ... N )  e. 
_V
3837rabex 4165 . . . . . . . . . . . . . . 15  |-  { n  e.  ( 1 ... N
)  |  ( k  e.  Prime  /\  k  ||  n ) }  e.  _V
3935, 36, 38fvmpt 5602 . . . . . . . . . . . . . 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 3258 . . . . . . . . . . . . . 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 3212 . . . . . . . . . . . 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 2626 . . . . . . . . . 10  |-  ( ph  ->  A. k  e.  ( ( K  +  1 ) ... N ) ( W `  k
)  C_  ( 1 ... N ) )
46 iunss 3943 . . . . . . . . . 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 3351 . . . . . . . 8  |-  ( ph  ->  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) )  C_  ( 1 ... N ) )
49 breq1 4026 . . . . . . . . . . . . . . . . . 18  |-  ( p  =  q  ->  (
p  ||  n  <->  q  ||  n ) )
5049notbid 285 . . . . . . . . . . . . . . . . 17  |-  ( p  =  q  ->  ( -.  p  ||  n  <->  -.  q  ||  n ) )
5150cbvralv 2764 . . . . . . . . . . . . . . . 16  |-  ( A. p  e.  ( Prime  \  ( 1 ... K
) )  -.  p  ||  n  <->  A. q  e.  ( Prime  \  ( 1 ... K ) )  -.  q  ||  n
)
52 breq2 4027 . . . . . . . . . . . . . . . . . 18  |-  ( n  =  x  ->  (
q  ||  n  <->  q  ||  x ) )
5352notbid 285 . . . . . . . . . . . . . . . . 17  |-  ( n  =  x  ->  ( -.  q  ||  n  <->  -.  q  ||  x ) )
5453ralbidv 2563 . . . . . . . . . . . . . . . 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 2925 . . . . . . . . . . . . . 14  |-  ( x  e.  M  <->  ( x  e.  ( 1 ... N
)  /\  A. q  e.  ( Prime  \  (
1 ... K ) )  -.  q  ||  x
) )
57 elun1 3342 . . . . . . . . . . . . . 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 2556 . . . . . . . . . . . 12  |-  ( E. q  e.  ( Prime  \  ( 1 ... K ) ) q 
||  x  <->  -.  A. q  e.  ( Prime  \  (
1 ... K ) )  -.  q  ||  x
)
62 eldifn 3299 . . . . . . . . . . . . . . . . . . . . . 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 3298 . . . . . . . . . . . . . . . . . . . . . . . . 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 12761 . . . . . . . . . . . . . . . . . . . . . . . 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 2373 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  e.  (
ZZ>= `  1 ) )
6915nnzd 10116 . . . . . . . . . . . . . . . . . . . . . . 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 10790 . . . . . . . . . . . . . . . . . . . . . 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 9761 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( ph  ->  K  e.  RR )
7574ad2antrr 706 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  K  e.  RR )
7667nnred 9761 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  e.  RR )
7775, 76ltnled 8966 . . . . . . . . . . . . . . . . . . . 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 12762 . . . . . . . . . . . . . . . . . . . . 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 10067 . . . . . . . . . . . . . . . . . . . 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 10819 . . . . . . . . . . . . . . . . . . . . 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 9761 . . . . . . . . . . . . . . . . . . 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 12574 . . . . . . . . . . . . . . . . . . . . 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 10800 . . . . . . . . . . . . . . . . . . . 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 8973 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  <_  N
)
9569peano2zd 10120 . . . . . . . . . . . . . . . . . . . 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 10116 . . . . . . . . . . . . . . . . . . . 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 10788 . . . . . . . . . . . . . . . . . . 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 1182 . . . . . . . . . . . . . . . . . 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 2923 . . . . . . . . . . . . . . . . . . 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 2343 . . . . . . . . . . . . . . . . . . . . . 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 2780 . . . . . . . . . . . . . . . . . . . 20  |-  ( p  =  q  ->  { n  e.  ( 1 ... N
)  |  ( p  e.  Prime  /\  p  ||  n ) }  =  { n  e.  (
1 ... N )  |  ( q  e.  Prime  /\  q  ||  n ) } )
11037rabex 4165 . . . . . . . . . . . . . . . . . . . 20  |-  { n  e.  ( 1 ... N
)  |  ( q  e.  Prime  /\  q  ||  n ) }  e.  _V
111109, 36, 110fvmpt 5602 . . . . . . . . . . . . . . . . . . 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 2360 . . . . . . . . . . . . . . . . 17  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  x  e.  ( W `  q ) )
114 fveq2 5525 . . . . . . . . . . . . . . . . . . 19  |-  ( k  =  q  ->  ( W `  k )  =  ( W `  q ) )
115114eleq2d 2350 . . . . . . . . . . . . . . . . . 18  |-  ( k  =  q  ->  (
x  e.  ( W `
 k )  <->  x  e.  ( W `  q ) ) )
116115rspcev 2884 . . . . . . . . . . . . . . . . 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 3909 . . . . . . . . . . . . . . . 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 3343 . . . . . . . . . . . . . . 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 2667 . . . . . . . . . . . 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 3185 . . . . . . . 8  |-  ( ph  ->  ( 1 ... N
)  C_  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) ) )
12848, 127eqssd 3196 . . . . . . 7  |-  ( ph  ->  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) )  =  ( 1 ... N ) )
129128fveq2d 5529 . . . . . 6  |-  ( ph  ->  ( # `  ( M  u.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) )  =  ( # `  (
1 ... N ) ) )
1301nnnn0d 10018 . . . . . . 7  |-  ( ph  ->  N  e.  NN0 )
131 hashfz1 11345 . . . . . . 7  |-  ( N  e.  NN0  ->  ( # `  ( 1 ... N
) )  =  N )
132130, 131syl 15 . . . . . 6  |-  ( ph  ->  ( # `  (
1 ... N ) )  =  N )
133129, 132eqtr2d 2316 . . . . 5  |-  ( ph  ->  N  =  ( # `  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) ) ) )
1349a1i 10 . . . . . 6  |-  ( ph  ->  M  e.  Fin )
135 ssfi 7083 . . . . . . 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 3459 . . . . . . . . . . . . . . . . . 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 3358 . . . . . . . . . . . . . . . . . . . 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 9687 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( ph  ->  K  <  ( K  +  1 ) )
144 fzdisj 10817 . . . . . . . . . . . . . . . . . . . . . 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 2350 . . . . . . . . . . . . . . . . . . 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 3162 . . . . . . . . . . . . . . . . 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 4027 . . . . . . . . . . . . . . . . . . . . 21  |-  ( n  =  x  ->  (
p  ||  n  <->  p  ||  x
) )
153152notbid 285 . . . . . . . . . . . . . . . . . . . 20  |-  ( n  =  x  ->  ( -.  p  ||  n  <->  -.  p  ||  x ) )
154153ralbidv 2563 . . . . . . . . . . . . . . . . . . 19  |-  ( n  =  x  ->  ( A. p  e.  ( Prime  \  ( 1 ... K ) )  -.  p  ||  n  <->  A. p  e.  ( Prime  \  (
1 ... K ) )  -.  p  ||  x
) )
155154, 5elrab2 2925 . . . . . . . . . . . . . . . . . 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 4026 . . . . . . . . . . . . . . . . . 18  |-  ( p  =  k  ->  (
p  ||  x  <->  k  ||  x ) )
159158notbid 285 . . . . . . . . . . . . . . . . 17  |-  ( p  =  k  ->  ( -.  p  ||  x  <->  -.  k  ||  x ) )
160159rspcv 2880 . . . . . . . . . . . . . . . 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 2350 . . . . . . . . . . . . . 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 4027 . . . . . . . . . . . . . . . . 17  |-  ( n  =  x  ->  (
k  ||  n  <->  k  ||  x ) )
169168anbi2d 684 . . . . . . . . . . . . . . . 16  |-  ( n  =  x  ->  (
( k  e.  Prime  /\  k  ||  n )  <-> 
( k  e.  Prime  /\  k  ||  x ) ) )
170169elrab 2923 . . . . . . . . . . . . . . 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 2646 . . . . . . . . . . 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 3358 . . . . . . . 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 3489 . . . . . 6  |-  ( ph  ->  ( M  i^i  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) )  =  (/) )
182 hashun 11364 . . . . . 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 1182 . . . . 5  |-  ( ph  ->  ( # `  ( M  u.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) )  =  ( ( # `  M )  +  (
# `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) ) )
18425, 133, 1833eqtrd 2319 . . . 4  |-  ( ph  ->  ( ( N  / 
2 )  +  ( N  /  2 ) )  =  ( (
# `  M )  +  ( # `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) ) )
185 hashcl 11350 . . . . . . 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 10019 . . . . 5  |-  ( ph  ->  ( # `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) )  e.  RR )
188 fzfid 11035 . . . . . . . 8  |-  ( ph  ->  ( ( K  + 
1 ) ... N
)  e.  Fin )
18927, 30sylan 457 . . . . . . . . . 10  |-  ( (
ph  /\  k  e.  ( ZZ>= `  ( K  +  1 ) ) )  ->  k  e.  NN )
190 nnrecre 9782 . . . . . . . . . . 11  |-  ( k  e.  NN  ->  (
1  /  k )  e.  RR )
191 0re 8838 . . . . . . . . . . 11  |-  0  e.  RR
192 ifcl 3601 . . . . . . . . . . 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 12207 . . . . . . 7  |-  ( ph  -> 
sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 )  e.  RR )
1972, 196remulcld 8863 . . . . . 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 12966 . . . . . . 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 10241 . . . . . . . . . 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 10071 . . . . . . . . . 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 10810 . . . . . . . . . 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 9827 . . . . . . . . . 10  |-  0  <_  0
21024mul01d 9011 . . . . . . . . . 10  |-  ( ph  ->  ( N  x.  0 )  =  0 )
211209, 210syl5breqr 4059 . . . . . . . . 9  |-  ( ph  ->  0  <_  ( N  x.  0 ) )
212 iuneq1 3918 . . . . . . . . . . . . 13  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k )  =  U_ k  e.  (/)  ( W `
 k ) )
213 0iun 3959 . . . . . . . . . . . . 13  |-  U_ k  e.  (/)  ( W `  k )  =  (/)
214212, 213syl6eq 2331 . . . . . . . . . . . 12  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k )  =  (/) )
215214fveq2d 5529 . . . . . . . . . . 11  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  ( # `  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) )  =  (
# `  (/) ) )
216 hash0 11355 . . . . . . . . . . 11  |-  ( # `  (/) )  =  0
217215, 216syl6eq 2331 . . . . . . . . . 10  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  ( # `  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) )  =  0 )
218 sumeq1 12162 . . . . . . . . . . . 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 12194 . . . . . . . . . . . 12  |-  sum_ k  e.  (/)  if ( k  e.  Prime ,  ( 1  /  k ) ,  0 )  =  0
220218, 219syl6eq 2331 . . . . . . . . . . 11  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  sum_ k  e.  ( ( K  + 
1 ) ... N
) if ( k  e.  Prime ,  ( 1  /  k ) ,  0 )  =  0 )
221220oveq2d 5874 . . . . . . . . . 10  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  ( N  x.  sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 ) )  =  ( N  x.  0 ) )
222217, 221breq12d 4036 . . . . . . . . 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 10249 . . . . . . . 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 2283 . . . . . . . . . 10  |-  ( ZZ>= `  ( K  +  1
) )  =  (
ZZ>= `  ( K  + 
1 ) )
229 eleq1 2343 . . . . . . . . . . . . 13  |-  ( n  =  k  ->  (
n  e.  Prime  <->  k  e.  Prime ) )
230 oveq2 5866 . . . . . . . . . . . . 13  |-  ( n  =  k  ->  (
1  /  n )  =  ( 1  / 
k ) )
231 eqidd 2284 . . . . . . . . . . . . 13  |-  ( n  =  k  ->  0  =  0 )
232229, 230, 231ifbieq12d 3587 . . . . . . . . . . . 12  |-  ( n  =  k  ->  if ( n  e.  Prime ,  ( 1  /  n
) ,  0 )  =  if ( k  e.  Prime ,  ( 1  /  k ) ,  0 ) )
233 ovex 5883 . . . . . . . . . . . . 13  |-  ( 1  /  k )  e. 
_V
234 c0ex 8832 . . . . . . . . . . . . 13  |-  0  e.  _V
235233, 234ifex 3623 . . . . . . . . . . . 12  |-  if ( k  e.  Prime ,  ( 1  /  k ) ,  0 )  e. 
_V
236232, 198, 235fvmpt 5602 . . . . . . . . . . 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 8861 . . . . . . . . . . . . . 14  |-  ( k  e.  NN  ->  if ( k  e.  Prime ,  ( 1  /  k
) ,  0 )  e.  CC )
239236, 238eqeltrd 2357 . . . . . . . . . . . . 13  |-  ( k  e.  NN  ->  ( F `  k )  e.  CC )
240239adantl 452 . . . . . . . . . . . 12  |-  ( (
ph  /\  k  e.  NN )  ->  ( F `
 k )  e.  CC )
24129, 27, 240iserex 12130 . . . . . . . . . . 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 12228 . . . . . . . . 9  |-  ( ph  -> 
sum_ k  e.  (
ZZ>= `  ( K  + 
1 ) ) if ( k  e.  Prime ,  ( 1  /  k
) ,  0 )  e.  RR )
244 1re 8837 . . . . . . . . . . 11  |-  1  e.  RR
245 rehalfcl 9938 . . . . . . . . . . 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 10832 . . . . . . . . . . 11  |-  ( ( K  +  1 ) ... N )  C_  ( ZZ>= `  ( K  +  1 ) )
249248a1i 10 . . . . . . . . . 10  |-  ( ph  ->  ( ( K  + 
1 ) ... N
)  C_  ( ZZ>= `  ( K  +  1
) ) )
250 nnrp 10363 . . . . . . . . . . . . . 14  |-  ( k  e.  NN  ->  k  e.  RR+ )
251250rpreccld 10400 . . . . . . . . . . . . 13  |-  ( k  e.  NN  ->  (
1  /  k )  e.  RR+ )
252251rpge0d 10394 . . . . . . . . . . . 12  |-  ( k  e.  NN  ->  0  <_  ( 1  /  k
) )
253 breq2 4027 . . . . . . . . . . . . 13  |-  ( ( 1  /  k )  =  if ( k  e.  Prime ,  ( 1  /  k ) ,  0 )  ->  (
0  <_  ( 1  /  k )  <->  0  <_  if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) ) )
254 breq2 4027 . . . . . . . . . . . . 13  |-  ( 0  =  if ( k  e.  Prime ,  ( 1  /  k ) ,  0 )  ->  (
0  <_  0  <->  0  <_  if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) ) )
255253, 254ifboth 3596 . . . . . . . . . . . 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 12304 . . . . . . . . 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 8974 . . . . . . . 8  |-  ( ph  -> 
sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 )  <  (
1  /  2 ) )
2601nngt0d 9789 . . . . . . . . 9  |-  ( ph  ->  0  <  N )
261 ltmul2 9607 . . . . . . . . 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 1186 . . . . . . . 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 9816 . . . . . . . . 9  |-  2  e.  CC
265 2ne0 9829 . . . . . . . . 9  |-  2  =/=  0
266 divrec 9440 . . . . . . . . 9  |-  ( ( N  e.  CC  /\  2  e.  CC  /\  2  =/=  0 )  ->  ( N  /  2 )  =  ( N  x.  (
1  /  2 ) ) )
267264, 265, 266mp3an23 1269 . . . . . . . 8  |-  ( N  e.  CC  ->  ( N  /  2 )  =  ( N  x.  (
1  /  2 ) ) )
26824, 267syl 15 . . . . . . 7  |-  ( ph  ->  ( N  /  2
)  =  ( N  x.  ( 1  / 
2 ) ) )
269263, 268breqtrrd 4049 . . . . . 6  |-  ( ph  ->  ( N  x.  sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) )  <  ( N  /  2 ) )
270187, 197, 3, 227, 269lelttrd 8974 . . . . 5  |-  ( ph  ->  ( # `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) )  < 
( N  /  2
) )
271187, 3, 13, 270ltadd2dd 8975 . . . 4  |-  ( ph  ->  ( ( # `  M
)  +  ( # `  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) ) )  < 
( ( # `  M
)  +  ( N  /  2 ) ) )
272184, 271eqbrtrd 4043 . . 3  |-  ( ph  ->  ( ( N  / 
2 )  +  ( N  /  2 ) )  <  ( (
# `  M )  +  ( N  / 
2 ) ) )
2733, 13, 3ltadd1d 9365 . . 3  |-  ( ph  ->  ( ( N  / 
2 )  <  ( # `
 M )  <->  ( ( N  /  2 )  +  ( N  /  2
) )  <  (
( # `  M )  +  ( N  / 
2 ) ) ) )
274272, 273mpbird 223 . 2  |-  ( ph  ->  ( N  /  2
)  <  ( # `  M
) )
275 oveq1 5865 . . . . . . . 8  |-  ( k  =  r  ->  (
k ^ 2 )  =  ( r ^
2 ) )
276275breq1d 4033 . . . . . . 7  |-  ( k  =  r  ->  (
( k ^ 2 )  ||  x  <->  ( r ^ 2 )  ||  x ) )
277276cbvrabv 2787 . . . . . 6  |-  { k  e.  NN  |  ( k ^ 2 ) 
||  x }  =  { r  e.  NN  |  ( r ^
2 )  ||  x }
278 breq2 4027 . . . . . . 7  |-  ( x  =  n  ->  (
( r ^ 2 )  ||  x  <->  ( r ^ 2 )  ||  n ) )
279278rabbidv 2780 . . . . . 6  |-  ( x  =  n  ->  { r  e.  NN  |  ( r ^ 2 ) 
||  x }  =  { r  e.  NN  |  ( r ^
2 )  ||  n } )
280277, 279syl5eq 2327 . . . . 5  |-  ( x  =  n  ->  { k  e.  NN  |  ( k ^ 2 ) 
||  x }  =  { r  e.  NN  |  ( r ^
2 )  ||  n } )
281280supeq1d 7199 . . . 4  |-  ( x  =  n  ->  sup ( { k  e.  NN  |  ( k ^
2 )  ||  x } ,  RR ,  <  )  =  sup ( { r  e.  NN  |  ( r ^
2 )  ||  n } ,  RR ,  <  ) )
282281cbvmptv 4111 . . 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 12965 . 2  |-  ( ph  ->  ( # `  M
)  <_  ( (
2 ^ K )  x.  ( sqr `  N
) ) )
2843, 13, 23, 274, 283ltletrd 8976 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 1623    e. wcel 1684    =/= wne 2446   A.wral 2543   E.wrex 2544   {crab 2547    \ cdif 3149    u. cun 3150    i^i cin 3151    C_ wss 3152   (/)c0 3455   ifcif 3565   U_ciun 3905   class class class wbr 4023    e. cmpt 4077   dom cdm 4689   ` cfv 5255  (class class class)co 5858   Fincfn 6863   supcsup 7193   CCcc 8735   RRcr 8736   0cc0 8737   1c1 8738    + caddc 8740    x. cmul 8742    < clt 8867    <_ cle 8868    / cdiv 9423   NNcn 9746   2c2 9795   NN0cn0 9965   ZZcz 10024   ZZ>=cuz 10230   ...cfz 10782    seq cseq 11046   ^cexp 11104   #chash 11337   sqrcsqr 11718    ~~> cli 11958   sum_csu 12158    || cdivides 12531   Primecprime 12758
This theorem is referenced by:  prmreclem6  12968
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1533  ax-5 1544  ax-17 1603  ax-9 1635  ax-8 1643  ax-13 1686  ax-14 1688  ax-6 1703  ax-7 1708  ax-11 1715  ax-12 1866  ax-ext 2264  ax-rep 4131  ax-sep 4141  ax-nul 4149  ax-pow 4188  ax-pr 4214  ax-un 4512  ax-inf2 7342  ax-cnex 8793  ax-resscn 8794  ax-1cn 8795  ax-icn 8796  ax-addcl 8797  ax-addrcl 8798  ax-mulcl 8799  ax-mulrcl 8800  ax-mulcom 8801  ax-addass 8802  ax-mulass 8803  ax-distr 8804  ax-i2m1 8805  ax-1ne0 8806  ax-1rid 8807  ax-rnegex 8808  ax-rrecex 8809  ax-cnre 8810  ax-pre-lttri 8811  ax-pre-lttrn 8812  ax-pre-ltadd 8813  ax-pre-mulgt0 8814  ax-pre-sup 8815
This theorem depends on definitions:  df-bi 177  df-or 359  df-an 360  df-3or 935  df-3an 936  df-tru 1310  df-ex 1529  df-nf 1532  df-sb 1630  df-eu 2147  df-mo 2148  df-clab 2270  df-cleq 2276  df-clel 2279  df-nfc 2408  df-ne 2448  df-nel 2449  df-ral 2548  df-rex 2549  df-reu 2550  df-rmo 2551  df-rab 2552  df-v 2790  df-sbc 2992  df-csb 3082  df-dif 3155  df-un 3157  df-in 3159  df-ss 3166  df-pss 3168  df-nul 3456  df-if 3566  df-pw 3627  df-sn 3646  df-pr 3647  df-tp 3648  df-op 3649  df-uni 3828  df-int 3863  df-iun 3907  df-br 4024  df-opab 4078  df-mpt 4079  df-tr 4114  df-eprel 4305  df-id 4309  df-po 4314  df-so 4315  df-fr 4352  df-se 4353  df-we 4354  df-ord 4395  df-on 4396  df-lim 4397  df-suc 4398  df-om 4657  df-xp 4695  df-rel 4696  df-cnv 4697  df-co 4698  df-dm 4699  df-rn 4700  df-res 4701  df-ima 4702  df-iota 5219  df-fun 5257  df-fn 5258  df-f 5259  df-f1 5260  df-fo 5261  df-f1o 5262  df-fv 5263  df-isom 5264  df-ov 5861  df-oprab 5862  df-mpt2 5863  df-1st 6122  df-2nd 6123  df-riota 6304  df-recs 6388  df-rdg 6423  df-1o 6479  df-2o 6480  df-oadd 6483  df-er 6660  df-map 6774  df-pm 6775  df-en 6864  df-dom 6865  df-sdom 6866  df-fin 6867  df-sup 7194  df-oi 7225  df-card 7572  df-cda 7794  df-pnf 8869  df-mnf 8870  df-xr 8871  df-ltxr 8872  df-le 8873  df-sub 9039  df-neg 9040  df-div 9424  df-nn 9747  df-2 9804  df-3 9805  df-n0 9966  df-z 10025  df-uz 10231  df-q 10317  df-rp 10355  df-fz 10783  df-fzo 10871  df-fl 10925  df-mod 10974  df-seq 11047  df-exp 11105  df-hash 11338  df-cj 11584  df-re 11585  df-im 11586  df-sqr 11720  df-abs 11721  df-clim 11962  df-rlim 11963  df-sum 12159  df-dvds 12532  df-gcd 12686  df-prm 12759  df-pc 12890
  Copyright terms: Public domain W3C validator