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

Theorem prmreclem5 13243
Description: Lemma for prmrec 13245. 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 13242 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 9971 . . 3  |-  ( ph  ->  N  e.  RR )
32rehalfcld 10170 . 2  |-  ( ph  ->  ( N  /  2
)  e.  RR )
4 fzfi 11266 . . . . . 6  |-  ( 1 ... N )  e. 
Fin
5 prmrec.4 . . . . . . 7  |-  M  =  { n  e.  ( 1 ... N )  |  A. p  e.  ( Prime  \  (
1 ... K ) )  -.  p  ||  n }
6 ssrab2 3388 . . . . . . 7  |-  { n  e.  ( 1 ... N
)  |  A. p  e.  ( Prime  \  (
1 ... K ) )  -.  p  ||  n }  C_  ( 1 ... N )
75, 6eqsstri 3338 . . . . . 6  |-  M  C_  ( 1 ... N
)
8 ssfi 7288 . . . . . 6  |-  ( ( ( 1 ... N
)  e.  Fin  /\  M  C_  ( 1 ... N ) )  ->  M  e.  Fin )
94, 7, 8mp2an 654 . . . . 5  |-  M  e. 
Fin
10 hashcl 11594 . . . . 5  |-  ( M  e.  Fin  ->  ( # `
 M )  e. 
NN0 )
119, 10ax-mp 8 . . . 4  |-  ( # `  M )  e.  NN0
1211nn0rei 10188 . . 3  |-  ( # `  M )  e.  RR
1312a1i 11 . 2  |-  ( ph  ->  ( # `  M
)  e.  RR )
14 2nn 10089 . . . . 5  |-  2  e.  NN
15 prmrec.2 . . . . . 6  |-  ( ph  ->  K  e.  NN )
1615nnnn0d 10230 . . . . 5  |-  ( ph  ->  K  e.  NN0 )
17 nnexpcl 11349 . . . . 5  |-  ( ( 2  e.  NN  /\  K  e.  NN0 )  -> 
( 2 ^ K
)  e.  NN )
1814, 16, 17sylancr 645 . . . 4  |-  ( ph  ->  ( 2 ^ K
)  e.  NN )
1918nnred 9971 . . 3  |-  ( ph  ->  ( 2 ^ K
)  e.  RR )
201nnrpd 10603 . . . . 5  |-  ( ph  ->  N  e.  RR+ )
2120rpsqrcld 12169 . . . 4  |-  ( ph  ->  ( sqr `  N
)  e.  RR+ )
2221rpred 10604 . . 3  |-  ( ph  ->  ( sqr `  N
)  e.  RR )
2319, 22remulcld 9072 . 2  |-  ( ph  ->  ( ( 2 ^ K )  x.  ( sqr `  N ) )  e.  RR )
242recnd 9070 . . . . . 6  |-  ( ph  ->  N  e.  CC )
25242halvesd 10169 . . . . 5  |-  ( ph  ->  ( ( N  / 
2 )  +  ( N  /  2 ) )  =  N )
267a1i 11 . . . . . . . . 9  |-  ( ph  ->  M  C_  ( 1 ... N ) )
2715peano2nnd 9973 . . . . . . . . . . . . 13  |-  ( ph  ->  ( K  +  1 )  e.  NN )
28 elfzuz 11011 . . . . . . . . . . . . 13  |-  ( k  e.  ( ( K  +  1 ) ... N )  ->  k  e.  ( ZZ>= `  ( K  +  1 ) ) )
29 nnuz 10477 . . . . . . . . . . . . . 14  |-  NN  =  ( ZZ>= `  1 )
3029uztrn2 10459 . . . . . . . . . . . . 13  |-  ( ( ( K  +  1 )  e.  NN  /\  k  e.  ( ZZ>= `  ( K  +  1
) ) )  -> 
k  e.  NN )
3127, 28, 30syl2an 464 . . . . . . . . . . . 12  |-  ( (
ph  /\  k  e.  ( ( K  + 
1 ) ... N
) )  ->  k  e.  NN )
32 eleq1 2464 . . . . . . . . . . . . . . . . 17  |-  ( p  =  k  ->  (
p  e.  Prime  <->  k  e.  Prime ) )
33 breq1 4175 . . . . . . . . . . . . . . . . 17  |-  ( p  =  k  ->  (
p  ||  n  <->  k  ||  n ) )
3432, 33anbi12d 692 . . . . . . . . . . . . . . . 16  |-  ( p  =  k  ->  (
( p  e.  Prime  /\  p  ||  n )  <-> 
( k  e.  Prime  /\  k  ||  n ) ) )
3534rabbidv 2908 . . . . . . . . . . . . . . 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 6065 . . . . . . . . . . . . . . . 16  |-  ( 1 ... N )  e. 
_V
3837rabex 4314 . . . . . . . . . . . . . . 15  |-  { n  e.  ( 1 ... N
)  |  ( k  e.  Prime  /\  k  ||  n ) }  e.  _V
3935, 36, 38fvmpt 5765 . . . . . . . . . . . . . 14  |-  ( k  e.  NN  ->  ( W `  k )  =  { n  e.  ( 1 ... N )  |  ( k  e. 
Prime  /\  k  ||  n
) } )
4039adantl 453 . . . . . . . . . . . . 13  |-  ( (
ph  /\  k  e.  NN )  ->  ( W `
 k )  =  { n  e.  ( 1 ... N )  |  ( k  e. 
Prime  /\  k  ||  n
) } )
41 ssrab2 3388 . . . . . . . . . . . . 13  |-  { n  e.  ( 1 ... N
)  |  ( k  e.  Prime  /\  k  ||  n ) }  C_  ( 1 ... N
)
4240, 41syl6eqss 3358 . . . . . . . . . . . 12  |-  ( (
ph  /\  k  e.  NN )  ->  ( W `
 k )  C_  ( 1 ... N
) )
4331, 42syldan 457 . . . . . . . . . . 11  |-  ( (
ph  /\  k  e.  ( ( K  + 
1 ) ... N
) )  ->  ( W `  k )  C_  ( 1 ... N
) )
4443ralrimiva 2749 . . . . . . . . . 10  |-  ( ph  ->  A. k  e.  ( ( K  +  1 ) ... N ) ( W `  k
)  C_  ( 1 ... N ) )
45 iunss 4092 . . . . . . . . . 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 204 . . . . . . . . 9  |-  ( ph  ->  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
)  C_  ( 1 ... N ) )
4726, 46unssd 3483 . . . . . . . 8  |-  ( ph  ->  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) )  C_  ( 1 ... N ) )
48 breq1 4175 . . . . . . . . . . . . . . . . . 18  |-  ( p  =  q  ->  (
p  ||  n  <->  q  ||  n ) )
4948notbid 286 . . . . . . . . . . . . . . . . 17  |-  ( p  =  q  ->  ( -.  p  ||  n  <->  -.  q  ||  n ) )
5049cbvralv 2892 . . . . . . . . . . . . . . . 16  |-  ( A. p  e.  ( Prime  \  ( 1 ... K
) )  -.  p  ||  n  <->  A. q  e.  ( Prime  \  ( 1 ... K ) )  -.  q  ||  n
)
51 breq2 4176 . . . . . . . . . . . . . . . . . 18  |-  ( n  =  x  ->  (
q  ||  n  <->  q  ||  x ) )
5251notbid 286 . . . . . . . . . . . . . . . . 17  |-  ( n  =  x  ->  ( -.  q  ||  n  <->  -.  q  ||  x ) )
5352ralbidv 2686 . . . . . . . . . . . . . . . 16  |-  ( n  =  x  ->  ( A. q  e.  ( Prime  \  ( 1 ... K ) )  -.  q  ||  n  <->  A. q  e.  ( Prime  \  (
1 ... K ) )  -.  q  ||  x
) )
5450, 53syl5bb 249 . . . . . . . . . . . . . . 15  |-  ( n  =  x  ->  ( A. p  e.  ( Prime  \  ( 1 ... K ) )  -.  p  ||  n  <->  A. q  e.  ( Prime  \  (
1 ... K ) )  -.  q  ||  x
) )
5554, 5elrab2 3054 . . . . . . . . . . . . . 14  |-  ( x  e.  M  <->  ( x  e.  ( 1 ... N
)  /\  A. q  e.  ( Prime  \  (
1 ... K ) )  -.  q  ||  x
) )
56 elun1 3474 . . . . . . . . . . . . . 14  |-  ( x  e.  M  ->  x  e.  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) ) )
5755, 56sylbir 205 . . . . . . . . . . . . 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 424 . . . . . . . . . . . 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 453 . . . . . . . . . . 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 2679 . . . . . . . . . . . 12  |-  ( E. q  e.  ( Prime  \  ( 1 ... K ) ) q 
||  x  <->  -.  A. q  e.  ( Prime  \  (
1 ... K ) )  -.  q  ||  x
)
61 eldifn 3430 . . . . . . . . . . . . . . . . . . . . 21  |-  ( q  e.  ( Prime  \  (
1 ... K ) )  ->  -.  q  e.  ( 1 ... K
) )
6261ad2antrl 709 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  -.  q  e.  ( 1 ... K
) )
63 eldifi 3429 . . . . . . . . . . . . . . . . . . . . . . . 24  |-  ( q  e.  ( Prime  \  (
1 ... K ) )  ->  q  e.  Prime )
6463ad2antrl 709 . . . . . . . . . . . . . . . . . . . . . . 23  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  e.  Prime )
65 prmnn 13037 . . . . . . . . . . . . . . . . . . . . . . 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 2494 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  e.  (
ZZ>= `  1 ) )
6815nnzd 10330 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( ph  ->  K  e.  ZZ )
6968ad2antrr 707 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  K  e.  ZZ )
70 elfz5 11007 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( q  e.  ( ZZ>= ` 
1 )  /\  K  e.  ZZ )  ->  (
q  e.  ( 1 ... K )  <->  q  <_  K ) )
7167, 69, 70syl2anc 643 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  ( q  e.  ( 1 ... K
)  <->  q  <_  K
) )
7262, 71mtbid 292 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  -.  q  <_  K )
7315nnred 9971 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ph  ->  K  e.  RR )
7473ad2antrr 707 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  K  e.  RR )
7566nnred 9971 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  e.  RR )
7674, 75ltnled 9176 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  ( K  < 
q  <->  -.  q  <_  K ) )
7772, 76mpbird 224 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  K  <  q
)
78 prmz 13038 . . . . . . . . . . . . . . . . . . . 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 10281 . . . . . . . . . . . . . . . . . . 19  |-  ( ( K  e.  ZZ  /\  q  e.  ZZ )  ->  ( K  <  q  <->  ( K  +  1 )  <_  q ) )
8169, 79, 80syl2anc 643 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  ( K  < 
q  <->  ( K  + 
1 )  <_  q
) )
8277, 81mpbid 202 . . . . . . . . . . . . . . . . 17  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  ( K  + 
1 )  <_  q
)
83 elfznn 11036 . . . . . . . . . . . . . . . . . . . 20  |-  ( x  e.  ( 1 ... N )  ->  x  e.  NN )
8483ad2antlr 708 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  x  e.  NN )
8584nnred 9971 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  x  e.  RR )
862ad2antrr 707 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  N  e.  RR )
87 simprr 734 . . . . . . . . . . . . . . . . . . 19  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  ||  x
)
88 dvdsle 12850 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( q  e.  ZZ  /\  x  e.  NN )  ->  ( q  ||  x  ->  q  <_  x )
)
8979, 84, 88syl2anc 643 . . . . . . . . . . . . . . . . . . 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 11017 . . . . . . . . . . . . . . . . . . 19  |-  ( x  e.  ( 1 ... N )  ->  x  <_  N )
9291ad2antlr 708 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  x  <_  N
)
9375, 85, 86, 90, 92letrd 9183 . . . . . . . . . . . . . . . . 17  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  <_  N
)
9468peano2zd 10334 . . . . . . . . . . . . . . . . . . 19  |-  ( ph  ->  ( K  +  1 )  e.  ZZ )
9594ad2antrr 707 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  ( K  + 
1 )  e.  ZZ )
961nnzd 10330 . . . . . . . . . . . . . . . . . . 19  |-  ( ph  ->  N  e.  ZZ )
9796ad2antrr 707 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  N  e.  ZZ )
98 elfz 11005 . . . . . . . . . . . . . . . . . 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 1184 . . . . . . . . . . . . . . . . 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 889 . . . . . . . . . . . . . . . 16  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  e.  ( ( K  +  1 ) ... N ) )
101 simplr 732 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  x  e.  ( 1 ... N ) )
10264, 87jca 519 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  ( q  e. 
Prime  /\  q  ||  x
) )
10351anbi2d 685 . . . . . . . . . . . . . . . . . . 19  |-  ( n  =  x  ->  (
( q  e.  Prime  /\  q  ||  n )  <-> 
( q  e.  Prime  /\  q  ||  x ) ) )
104103elrab 3052 . . . . . . . . . . . . . . . . . 18  |-  ( x  e.  { n  e.  ( 1 ... N
)  |  ( q  e.  Prime  /\  q  ||  n ) }  <->  ( x  e.  ( 1 ... N
)  /\  ( q  e.  Prime  /\  q  ||  x ) ) )
105101, 102, 104sylanbrc 646 . . . . . . . . . . . . . . . . 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 2464 . . . . . . . . . . . . . . . . . . . . 21  |-  ( p  =  q  ->  (
p  e.  Prime  <->  q  e.  Prime ) )
107106, 48anbi12d 692 . . . . . . . . . . . . . . . . . . . 20  |-  ( p  =  q  ->  (
( p  e.  Prime  /\  p  ||  n )  <-> 
( q  e.  Prime  /\  q  ||  n ) ) )
108107rabbidv 2908 . . . . . . . . . . . . . . . . . . 19  |-  ( p  =  q  ->  { n  e.  ( 1 ... N
)  |  ( p  e.  Prime  /\  p  ||  n ) }  =  { n  e.  (
1 ... N )  |  ( q  e.  Prime  /\  q  ||  n ) } )
10937rabex 4314 . . . . . . . . . . . . . . . . . . 19  |-  { n  e.  ( 1 ... N
)  |  ( q  e.  Prime  /\  q  ||  n ) }  e.  _V
110108, 36, 109fvmpt 5765 . . . . . . . . . . . . . . . . . 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 2481 . . . . . . . . . . . . . . . 16  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  x  e.  ( W `  q ) )
113 fveq2 5687 . . . . . . . . . . . . . . . . . 18  |-  ( k  =  q  ->  ( W `  k )  =  ( W `  q ) )
114113eleq2d 2471 . . . . . . . . . . . . . . . . 17  |-  ( k  =  q  ->  (
x  e.  ( W `
 k )  <->  x  e.  ( W `  q ) ) )
115114rspcev 3012 . . . . . . . . . . . . . . . 16  |-  ( ( q  e.  ( ( K  +  1 ) ... N )  /\  x  e.  ( W `  q ) )  ->  E. k  e.  (
( K  +  1 ) ... N ) x  e.  ( W `
 k ) )
116100, 112, 115syl2anc 643 . . . . . . . . . . . . . . 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 4057 . . . . . . . . . . . . . . 15  |-  ( x  e.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k )  <->  E. k  e.  ( ( K  + 
1 ) ... N
) x  e.  ( W `  k ) )
118116, 117sylibr 204 . . . . . . . . . . . . . 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 3475 . . . . . . . . . . . . . 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 2791 . . . . . . . . . . . 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 210 . . . . . . . . . . 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 152 . . . . . . . . . 10  |-  ( (
ph  /\  x  e.  ( 1 ... N
) )  ->  x  e.  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) ) )
124123ex 424 . . . . . . . . 9  |-  ( ph  ->  ( x  e.  ( 1 ... N )  ->  x  e.  ( M  u.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) ) )
125124ssrdv 3314 . . . . . . . 8  |-  ( ph  ->  ( 1 ... N
)  C_  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) ) )
12647, 125eqssd 3325 . . . . . . 7  |-  ( ph  ->  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) )  =  ( 1 ... N ) )
127126fveq2d 5691 . . . . . 6  |-  ( ph  ->  ( # `  ( M  u.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) )  =  ( # `  (
1 ... N ) ) )
1281nnnn0d 10230 . . . . . . 7  |-  ( ph  ->  N  e.  NN0 )
129 hashfz1 11585 . . . . . . 7  |-  ( N  e.  NN0  ->  ( # `  ( 1 ... N
) )  =  N )
130128, 129syl 16 . . . . . 6  |-  ( ph  ->  ( # `  (
1 ... N ) )  =  N )
131127, 130eqtr2d 2437 . . . . 5  |-  ( ph  ->  N  =  ( # `  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) ) ) )
1329a1i 11 . . . . . 6  |-  ( ph  ->  M  e.  Fin )
133 ssfi 7288 . . . . . . 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 645 . . . . . 6  |-  ( ph  ->  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
)  e.  Fin )
135 simprr 734 . . . . . . . . . . . . . . . . 17  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  k  e.  Prime )
136 noel 3592 . . . . . . . . . . . . . . . . . 18  |-  -.  k  e.  (/)
137 simprl 733 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  k  e.  ( ( K  +  1 ) ... N ) )
138137biantrud 494 . . . . . . . . . . . . . . . . . . . 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 3490 . . . . . . . . . . . . . . . . . . . 20  |-  ( k  e.  ( ( 1 ... K )  i^i  ( ( K  + 
1 ) ... N
) )  <->  ( k  e.  ( 1 ... K
)  /\  k  e.  ( ( K  + 
1 ) ... N
) ) )
140138, 139syl6bbr 255 . . . . . . . . . . . . . . . . . . 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 9897 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( ph  ->  K  <  ( K  +  1 ) )
142 fzdisj 11034 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( K  <  ( K  + 
1 )  ->  (
( 1 ... K
)  i^i  ( ( K  +  1 ) ... N ) )  =  (/) )
143141, 142syl 16 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ph  ->  ( ( 1 ... K )  i^i  (
( K  +  1 ) ... N ) )  =  (/) )
144143ad2antrr 707 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  ( ( 1 ... K )  i^i  ( ( K  + 
1 ) ... N
) )  =  (/) )
145144eleq2d 2471 . . . . . . . . . . . . . . . . . . 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 245 . . . . . . . . . . . . . . . . . 18  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  ( k  e.  ( 1 ... K
)  <->  k  e.  (/) ) )
147136, 146mtbiri 295 . . . . . . . . . . . . . . . . 17  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  -.  k  e.  ( 1 ... K
) )
148135, 147eldifd 3291 . . . . . . . . . . . . . . . 16  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  k  e.  ( Prime  \  ( 1 ... K ) ) )
149 breq2 4176 . . . . . . . . . . . . . . . . . . . . 21  |-  ( n  =  x  ->  (
p  ||  n  <->  p  ||  x
) )
150149notbid 286 . . . . . . . . . . . . . . . . . . . 20  |-  ( n  =  x  ->  ( -.  p  ||  n  <->  -.  p  ||  x ) )
151150ralbidv 2686 . . . . . . . . . . . . . . . . . . 19  |-  ( n  =  x  ->  ( A. p  e.  ( Prime  \  ( 1 ... K ) )  -.  p  ||  n  <->  A. p  e.  ( Prime  \  (
1 ... K ) )  -.  p  ||  x
) )
152151, 5elrab2 3054 . . . . . . . . . . . . . . . . . 18  |-  ( x  e.  M  <->  ( x  e.  ( 1 ... N
)  /\  A. p  e.  ( Prime  \  (
1 ... K ) )  -.  p  ||  x
) )
153152simprbi 451 . . . . . . . . . . . . . . . . 17  |-  ( x  e.  M  ->  A. p  e.  ( Prime  \  (
1 ... K ) )  -.  p  ||  x
)
154153ad2antlr 708 . . . . . . . . . . . . . . . 16  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  A. p  e.  ( Prime  \  ( 1 ... K ) )  -.  p  ||  x
)
155 breq1 4175 . . . . . . . . . . . . . . . . . 18  |-  ( p  =  k  ->  (
p  ||  x  <->  k  ||  x ) )
156155notbid 286 . . . . . . . . . . . . . . . . 17  |-  ( p  =  k  ->  ( -.  p  ||  x  <->  -.  k  ||  x ) )
157156rspcv 3008 . . . . . . . . . . . . . . . 16  |-  ( k  e.  ( Prime  \  (
1 ... K ) )  ->  ( A. p  e.  ( Prime  \  (
1 ... K ) )  -.  p  ||  x  ->  -.  k  ||  x
) )
158148, 154, 157sylc 58 . . . . . . . . . . . . . . 15  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  -.  k  ||  x )
159158expr 599 . . . . . . . . . . . . . 14  |-  ( ( ( ph  /\  x  e.  M )  /\  k  e.  ( ( K  + 
1 ) ... N
) )  ->  (
k  e.  Prime  ->  -.  k  ||  x ) )
160 imnan 412 . . . . . . . . . . . . . 14  |-  ( ( k  e.  Prime  ->  -.  k  ||  x )  <->  -.  ( k  e.  Prime  /\  k  ||  x ) )
161159, 160sylib 189 . . . . . . . . . . . . 13  |-  ( ( ( ph  /\  x  e.  M )  /\  k  e.  ( ( K  + 
1 ) ... N
) )  ->  -.  ( k  e.  Prime  /\  k  ||  x ) )
16231adantlr 696 . . . . . . . . . . . . . . . 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 2471 . . . . . . . . . . . . . 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 4176 . . . . . . . . . . . . . . . . 17  |-  ( n  =  x  ->  (
k  ||  n  <->  k  ||  x ) )
166165anbi2d 685 . . . . . . . . . . . . . . . 16  |-  ( n  =  x  ->  (
( k  e.  Prime  /\  k  ||  n )  <-> 
( k  e.  Prime  /\  k  ||  x ) ) )
167166elrab 3052 . . . . . . . . . . . . . . 15  |-  ( x  e.  { n  e.  ( 1 ... N
)  |  ( k  e.  Prime  /\  k  ||  n ) }  <->  ( x  e.  ( 1 ... N
)  /\  ( k  e.  Prime  /\  k  ||  x ) ) )
168167simprbi 451 . . . . . . . . . . . . . 14  |-  ( x  e.  { n  e.  ( 1 ... N
)  |  ( k  e.  Prime  /\  k  ||  n ) }  ->  ( k  e.  Prime  /\  k  ||  x ) )
169164, 168syl6bi 220 . . . . . . . . . . . . 13  |-  ( ( ( ph  /\  x  e.  M )  /\  k  e.  ( ( K  + 
1 ) ... N
) )  ->  (
x  e.  ( W `
 k )  -> 
( k  e.  Prime  /\  k  ||  x ) ) )
170161, 169mtod 170 . . . . . . . . . . . 12  |-  ( ( ( ph  /\  x  e.  M )  /\  k  e.  ( ( K  + 
1 ) ... N
) )  ->  -.  x  e.  ( W `  k ) )
171170nrexdv 2769 . . . . . . . . . . 11  |-  ( (
ph  /\  x  e.  M )  ->  -.  E. k  e.  ( ( K  +  1 ) ... N ) x  e.  ( W `  k ) )
172171, 117sylnibr 297 . . . . . . . . . 10  |-  ( (
ph  /\  x  e.  M )  ->  -.  x  e.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) )
173172ex 424 . . . . . . . . 9  |-  ( ph  ->  ( x  e.  M  ->  -.  x  e.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) ) )
174 imnan 412 . . . . . . . . 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 189 . . . . . . . 8  |-  ( ph  ->  -.  ( x  e.  M  /\  x  e. 
U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) ) )
176 elin 3490 . . . . . . . 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 297 . . . . . . 7  |-  ( ph  ->  -.  x  e.  ( M  i^i  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) )
178177eq0rdv 3622 . . . . . 6  |-  ( ph  ->  ( M  i^i  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) )  =  (/) )
179 hashun 11611 . . . . . 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 1184 . . . . 5  |-  ( ph  ->  ( # `  ( M  u.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) )  =  ( ( # `  M )  +  (
# `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) ) )
18125, 131, 1803eqtrd 2440 . . . 4  |-  ( ph  ->  ( ( N  / 
2 )  +  ( N  /  2 ) )  =  ( (
# `  M )  +  ( # `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) ) )
182 hashcl 11594 . . . . . . 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 10231 . . . . 5  |-  ( ph  ->  ( # `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) )  e.  RR )
185 fzfid 11267 . . . . . . . 8  |-  ( ph  ->  ( ( K  + 
1 ) ... N
)  e.  Fin )
18627, 30sylan 458 . . . . . . . . . 10  |-  ( (
ph  /\  k  e.  ( ZZ>= `  ( K  +  1 ) ) )  ->  k  e.  NN )
187 nnrecre 9992 . . . . . . . . . . 11  |-  ( k  e.  NN  ->  (
1  /  k )  e.  RR )
188 0re 9047 . . . . . . . . . . 11  |-  0  e.  RR
189 ifcl 3735 . . . . . . . . . . 11  |-  ( ( ( 1  /  k
)  e.  RR  /\  0  e.  RR )  ->  if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 )  e.  RR )
190187, 188, 189sylancl 644 . . . . . . . . . 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 461 . . . . . . . 8  |-  ( (
ph  /\  k  e.  ( ( K  + 
1 ) ... N
) )  ->  if ( k  e.  Prime ,  ( 1  /  k
) ,  0 )  e.  RR )
193185, 192fsumrecl 12483 . . . . . . 7  |-  ( ph  -> 
sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 )  e.  RR )
1942, 193remulcld 9072 . . . . . 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 13242 . . . . . . 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 10455 . . . . . . . . . 10  |-  ( ( N  e.  ZZ  /\  K  e.  ZZ )  ->  ( K  e.  (
ZZ>= `  N )  <->  N  <_  K ) )
20096, 68, 199syl2anc 643 . . . . . . . . 9  |-  ( ph  ->  ( K  e.  (
ZZ>= `  N )  <->  N  <_  K ) )
201 nnleltp1 10285 . . . . . . . . . 10  |-  ( ( N  e.  NN  /\  K  e.  NN )  ->  ( N  <_  K  <->  N  <  ( K  + 
1 ) ) )
2021, 15, 201syl2anc 643 . . . . . . . . 9  |-  ( ph  ->  ( N  <_  K  <->  N  <  ( K  + 
1 ) ) )
203 fzn 11027 . . . . . . . . . 10  |-  ( ( ( K  +  1 )  e.  ZZ  /\  N  e.  ZZ )  ->  ( N  <  ( K  +  1 )  <-> 
( ( K  + 
1 ) ... N
)  =  (/) ) )
20494, 96, 203syl2anc 643 . . . . . . . . 9  |-  ( ph  ->  ( N  <  ( K  +  1 )  <-> 
( ( K  + 
1 ) ... N
)  =  (/) ) )
205200, 202, 2043bitrd 271 . . . . . . . 8  |-  ( ph  ->  ( K  e.  (
ZZ>= `  N )  <->  ( ( K  +  1 ) ... N )  =  (/) ) )
206 0le0 10037 . . . . . . . . . 10  |-  0  <_  0
20724mul01d 9221 . . . . . . . . . 10  |-  ( ph  ->  ( N  x.  0 )  =  0 )
208206, 207syl5breqr 4208 . . . . . . . . 9  |-  ( ph  ->  0  <_  ( N  x.  0 ) )
209 iuneq1 4066 . . . . . . . . . . . . 13  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k )  =  U_ k  e.  (/)  ( W `
 k ) )
210 0iun 4108 . . . . . . . . . . . . 13  |-  U_ k  e.  (/)  ( W `  k )  =  (/)
211209, 210syl6eq 2452 . . . . . . . . . . . 12  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k )  =  (/) )
212211fveq2d 5691 . . . . . . . . . . 11  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  ( # `  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) )  =  (
# `  (/) ) )
213 hash0 11601 . . . . . . . . . . 11  |-  ( # `  (/) )  =  0
214212, 213syl6eq 2452 . . . . . . . . . 10  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  ( # `  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) )  =  0 )
215 sumeq1 12438 . . . . . . . . . . . 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 12470 . . . . . . . . . . . 12  |-  sum_ k  e.  (/)  if ( k  e.  Prime ,  ( 1  /  k ) ,  0 )  =  0
217215, 216syl6eq 2452 . . . . . . . . . . 11  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  sum_ k  e.  ( ( K  + 
1 ) ... N
) if ( k  e.  Prime ,  ( 1  /  k ) ,  0 )  =  0 )
218217oveq2d 6056 . . . . . . . . . 10  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  ( N  x.  sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 ) )  =  ( N  x.  0 ) )
219214, 218breq12d 4185 . . . . . . . . 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 214 . . . . . . . 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 207 . . . . . . 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 10463 . . . . . . . 8  |-  ( ( K  e.  ZZ  /\  N  e.  ZZ )  ->  ( N  e.  (
ZZ>= `  K )  \/  K  e.  ( ZZ>= `  N ) ) )
22368, 96, 222syl2anc 643 . . . . . . 7  |-  ( ph  ->  ( N  e.  (
ZZ>= `  K )  \/  K  e.  ( ZZ>= `  N ) ) )
224198, 221, 223mpjaod 371 . . . . . 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 2404 . . . . . . . . . 10  |-  ( ZZ>= `  ( K  +  1
) )  =  (
ZZ>= `  ( K  + 
1 ) )
226 eleq1 2464 . . . . . . . . . . . . 13  |-  ( n  =  k  ->  (
n  e.  Prime  <->  k  e.  Prime ) )
227 oveq2 6048 . . . . . . . . . . . . 13  |-  ( n  =  k  ->  (
1  /  n )  =  ( 1  / 
k ) )
228 eqidd 2405 . . . . . . . . . . . . 13  |-  ( n  =  k  ->  0  =  0 )
229226, 227, 228ifbieq12d 3721 . . . . . . . . . . . 12  |-  ( n  =  k  ->  if ( n  e.  Prime ,  ( 1  /  n
) ,  0 )  =  if ( k  e.  Prime ,  ( 1  /  k ) ,  0 ) )
230 ovex 6065 . . . . . . . . . . . . 13  |-  ( 1  /  k )  e. 
_V
231 c0ex 9041 . . . . . . . . . . . . 13  |-  0  e.  _V
232230, 231ifex 3757 . . . . . . . . . . . 12  |-  if ( k  e.  Prime ,  ( 1  /  k ) ,  0 )  e. 
_V
233229, 195, 232fvmpt 5765 . . . . . . . . . . 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 9070 . . . . . . . . . . . . . 14  |-  ( k  e.  NN  ->  if ( k  e.  Prime ,  ( 1  /  k
) ,  0 )  e.  CC )
236233, 235eqeltrd 2478 . . . . . . . . . . . . 13  |-  ( k  e.  NN  ->  ( F `  k )  e.  CC )
237236adantl 453 . . . . . . . . . . . 12  |-  ( (
ph  /\  k  e.  NN )  ->  ( F `
 k )  e.  CC )
23829, 27, 237iserex 12405 . . . . . . . . . . 11  |-  ( ph  ->  (  seq  1 (  +  ,  F )  e.  dom  ~~>  <->  seq  ( K  +  1 ) (  +  ,  F )  e.  dom  ~~>  ) )
239196, 238mpbid 202 . . . . . . . . . 10  |-  ( ph  ->  seq  ( K  + 
1 ) (  +  ,  F )  e. 
dom 
~~>  )
240225, 94, 234, 191, 239isumrecl 12504 . . . . . . . . 9  |-  ( ph  -> 
sum_ k  e.  (
ZZ>= `  ( K  + 
1 ) ) if ( k  e.  Prime ,  ( 1  /  k
) ,  0 )  e.  RR )
241 1re 9046 . . . . . . . . . . 11  |-  1  e.  RR
242241rehalfcli 10172 . . . . . . . . . 10  |-  ( 1  /  2 )  e.  RR
243242a1i 11 . . . . . . . . 9  |-  ( ph  ->  ( 1  /  2
)  e.  RR )
244 fzssuz 11049 . . . . . . . . . . 11  |-  ( ( K  +  1 ) ... N )  C_  ( ZZ>= `  ( K  +  1 ) )
245244a1i 11 . . . . . . . . . 10  |-  ( ph  ->  ( ( K  + 
1 ) ... N
)  C_  ( ZZ>= `  ( K  +  1
) ) )
246 nnrp 10577 . . . . . . . . . . . . . 14  |-  ( k  e.  NN  ->  k  e.  RR+ )
247246rpreccld 10614 . . . . . . . . . . . . 13  |-  ( k  e.  NN  ->  (
1  /  k )  e.  RR+ )
248247rpge0d 10608 . . . . . . . . . . . 12  |-  ( k  e.  NN  ->  0  <_  ( 1  /  k
) )
249 breq2 4176 . . . . . . . . . . . . 13  |-  ( ( 1  /  k )  =  if ( k  e.  Prime ,  ( 1  /  k ) ,  0 )  ->  (
0  <_  ( 1  /  k )  <->  0  <_  if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) ) )
250 breq2 4176 . . . . . . . . . . . . 13  |-  ( 0  =  if ( k  e.  Prime ,  ( 1  /  k ) ,  0 )  ->  (
0  <_  0  <->  0  <_  if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) ) )
251249, 250ifboth 3730 . . . . . . . . . . . 12  |-  ( ( 0  <_  ( 1  /  k )  /\  0  <_  0 )  -> 
0  <_  if (
k  e.  Prime ,  ( 1  /  k ) ,  0 ) )
252248, 206, 251sylancl 644 . . . . . . . . . . 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 12580 . . . . . . . . 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 9184 . . . . . . . 8  |-  ( ph  -> 
sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 )  <  (
1  /  2 ) )
2561nngt0d 9999 . . . . . . . . 9  |-  ( ph  ->  0  <  N )
257 ltmul2 9817 . . . . . . . . 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 1188 . . . . . . . 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 202 . . . . . . 7  |-  ( ph  ->  ( N  x.  sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) )  <  ( N  x.  ( 1  / 
2 ) ) )
260 2cn 10026 . . . . . . . . 9  |-  2  e.  CC
261 2ne0 10039 . . . . . . . . 9  |-  2  =/=  0
262 divrec 9650 . . . . . . . . 9  |-  ( ( N  e.  CC  /\  2  e.  CC  /\  2  =/=  0 )  ->  ( N  /  2 )  =  ( N  x.  (
1  /  2 ) ) )
263260, 261, 262mp3an23 1271 . . . . . . . 8  |-  ( N  e.  CC  ->  ( N  /  2 )  =  ( N  x.  (
1  /  2 ) ) )
26424, 263syl 16 . . . . . . 7  |-  ( ph  ->  ( N  /  2
)  =  ( N  x.  ( 1  / 
2 ) ) )
265259, 264breqtrrd 4198 . . . . . 6  |-  ( ph  ->  ( N  x.  sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) )  <  ( N  /  2 ) )
266184, 194, 3, 224, 265lelttrd 9184 . . . . 5  |-  ( ph  ->  ( # `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) )  < 
( N  /  2
) )
267184, 3, 13, 266ltadd2dd 9185 . . . 4  |-  ( ph  ->  ( ( # `  M
)  +  ( # `  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) ) )  < 
( ( # `  M
)  +  ( N  /  2 ) ) )
268181, 267eqbrtrd 4192 . . 3  |-  ( ph  ->  ( ( N  / 
2 )  +  ( N  /  2 ) )  <  ( (
# `  M )  +  ( N  / 
2 ) ) )
2693, 13, 3ltadd1d 9575 . . 3  |-  ( ph  ->  ( ( N  / 
2 )  <  ( # `
 M )  <->  ( ( N  /  2 )  +  ( N  /  2
) )  <  (
( # `  M )  +  ( N  / 
2 ) ) ) )
270268, 269mpbird 224 . 2  |-  ( ph  ->  ( N  /  2
)  <  ( # `  M
) )
271 oveq1 6047 . . . . . . . 8  |-  ( k  =  r  ->  (
k ^ 2 )  =  ( r ^
2 ) )
272271breq1d 4182 . . . . . . 7  |-  ( k  =  r  ->  (
( k ^ 2 )  ||  x  <->  ( r ^ 2 )  ||  x ) )
273272cbvrabv 2915 . . . . . 6  |-  { k  e.  NN  |  ( k ^ 2 ) 
||  x }  =  { r  e.  NN  |  ( r ^
2 )  ||  x }
274 breq2 4176 . . . . . . 7  |-  ( x  =  n  ->  (
( r ^ 2 )  ||  x  <->  ( r ^ 2 )  ||  n ) )
275274rabbidv 2908 . . . . . 6  |-  ( x  =  n  ->  { r  e.  NN  |  ( r ^ 2 ) 
||  x }  =  { r  e.  NN  |  ( r ^
2 )  ||  n } )
276273, 275syl5eq 2448 . . . . 5  |-  ( x  =  n  ->  { k  e.  NN  |  ( k ^ 2 ) 
||  x }  =  { r  e.  NN  |  ( r ^
2 )  ||  n } )
277276supeq1d 7409 . . . 4  |-  ( x  =  n  ->  sup ( { k  e.  NN  |  ( k ^
2 )  ||  x } ,  RR ,  <  )  =  sup ( { r  e.  NN  |  ( r ^
2 )  ||  n } ,  RR ,  <  ) )
278277cbvmptv 4260 . . 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 13241 . 2  |-  ( ph  ->  ( # `  M
)  <_  ( (
2 ^ K )  x.  ( sqr `  N
) ) )
2803, 13, 23, 270, 279ltletrd 9186 1  |-  ( ph  ->  ( N  /  2
)  <  ( (
2 ^ K )  x.  ( sqr `  N
) ) )
Colors of variables: wff set class
Syntax hints:   -. wn 3    -> wi 4    <-> wb 177    \/ wo 358    /\ wa 359    = wceq 1649    e. wcel 1721    =/= wne 2567   A.wral 2666   E.wrex 2667   {crab 2670    \ cdif 3277    u. cun 3278    i^i cin 3279    C_ wss 3280   (/)c0 3588   ifcif 3699   U_ciun 4053   class class class wbr 4172    e. cmpt 4226   dom cdm 4837   ` cfv 5413  (class class class)co 6040   Fincfn 7068   supcsup 7403   CCcc 8944   RRcr 8945   0cc0 8946   1c1 8947    + caddc 8949    x. cmul 8951    < clt 9076    <_ cle 9077    / cdiv 9633   NNcn 9956   2c2 10005   NN0cn0 10177   ZZcz 10238   ZZ>=cuz 10444   ...cfz 10999    seq cseq 11278   ^cexp 11337   #chash 11573   sqrcsqr 11993    ~~> cli 12233   sum_csu 12434    || cdivides 12807   Primecprime 13034
This theorem is referenced by:  prmreclem6  13244
This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1552  ax-5 1563  ax-17 1623  ax-9 1662  ax-8 1683  ax-13 1723  ax-14 1725  ax-6 1740  ax-7 1745  ax-11 1757  ax-12 1946  ax-ext 2385  ax-rep 4280  ax-sep 4290  ax-nul 4298  ax-pow 4337  ax-pr 4363  ax-un 4660  ax-inf2 7552  ax-cnex 9002  ax-resscn 9003  ax-1cn 9004  ax-icn 9005  ax-addcl 9006  ax-addrcl 9007  ax-mulcl 9008  ax-mulrcl 9009  ax-mulcom 9010  ax-addass 9011  ax-mulass 9012  ax-distr 9013  ax-i2m1 9014  ax-1ne0 9015  ax-1rid 9016  ax-rnegex 9017  ax-rrecex 9018  ax-cnre 9019  ax-pre-lttri 9020  ax-pre-lttrn 9021  ax-pre-ltadd 9022  ax-pre-mulgt0 9023  ax-pre-sup 9024
This theorem depends on definitions:  df-bi 178  df-or 360  df-an 361  df-3or 937  df-3an 938  df-tru 1325  df-ex 1548  df-nf 1551  df-sb 1656  df-eu 2258  df-mo 2259  df-clab 2391  df-cleq 2397  df-clel 2400  df-nfc 2529  df-ne 2569  df-nel 2570  df-ral 2671  df-rex 2672  df-reu 2673  df-rmo 2674  df-rab 2675  df-v 2918  df-sbc 3122  df-csb 3212  df-dif 3283  df-un 3285  df-in 3287  df-ss 3294  df-pss 3296  df-nul 3589  df-if 3700  df-pw 3761  df-sn 3780  df-pr 3781  df-tp 3782  df-op 3783  df-uni 3976  df-int 4011  df-iun 4055  df-br 4173  df-opab 4227  df-mpt 4228  df-tr 4263  df-eprel 4454  df-id 4458  df-po 4463  df-so 4464  df-fr 4501  df-se 4502  df-we 4503  df-ord 4544  df-on 4545  df-lim 4546  df-suc 4547  df-om 4805  df-xp 4843  df-rel 4844  df-cnv 4845  df-co 4846  df-dm 4847  df-rn 4848  df-res 4849  df-ima 4850  df-iota 5377  df-fun 5415  df-fn 5416  df-f 5417  df-f1 5418  df-fo 5419  df-f1o 5420  df-fv 5421  df-isom 5422  df-ov 6043  df-oprab 6044  df-mpt2 6045  df-1st 6308  df-2nd 6309  df-riota 6508  df-recs 6592  df-rdg 6627  df-1o 6683  df-2o 6684  df-oadd 6687  df-er 6864  df-map 6979  df-pm 6980  df-en 7069  df-dom 7070  df-sdom 7071  df-fin 7072  df-sup 7404  df-oi 7435  df-card 7782  df-cda 8004  df-pnf 9078  df-mnf 9079  df-xr 9080  df-ltxr 9081  df-le 9082  df-sub 9249  df-neg 9250  df-div 9634  df-nn 9957  df-2 10014  df-3 10015  df-n0 10178  df-z 10239  df-uz 10445  df-q 10531  df-rp 10569  df-fz 11000  df-fzo 11091  df-fl 11157  df-mod 11206  df-seq 11279  df-exp 11338  df-hash 11574  df-cj 11859  df-re 11860  df-im 11861  df-sqr 11995  df-abs 11996  df-clim 12237  df-rlim 12238  df-sum 12435  df-dvds 12808  df-gcd 12962  df-prm 13035  df-pc 13166
  Copyright terms: Public domain W3C validator