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

Theorem prmreclem5 13247
Description: Lemma for prmrec 13249. 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 13246 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 9975 . . 3  |-  ( ph  ->  N  e.  RR )
32rehalfcld 10174 . 2  |-  ( ph  ->  ( N  /  2
)  e.  RR )
4 fzfi 11270 . . . . . 6  |-  ( 1 ... N )  e. 
Fin
5 prmrec.4 . . . . . . 7  |-  M  =  { n  e.  ( 1 ... N )  |  A. p  e.  ( Prime  \  (
1 ... K ) )  -.  p  ||  n }
6 ssrab2 3392 . . . . . . 7  |-  { n  e.  ( 1 ... N
)  |  A. p  e.  ( Prime  \  (
1 ... K ) )  -.  p  ||  n }  C_  ( 1 ... N )
75, 6eqsstri 3342 . . . . . 6  |-  M  C_  ( 1 ... N
)
8 ssfi 7292 . . . . . 6  |-  ( ( ( 1 ... N
)  e.  Fin  /\  M  C_  ( 1 ... N ) )  ->  M  e.  Fin )
94, 7, 8mp2an 654 . . . . 5  |-  M  e. 
Fin
10 hashcl 11598 . . . . 5  |-  ( M  e.  Fin  ->  ( # `
 M )  e. 
NN0 )
119, 10ax-mp 8 . . . 4  |-  ( # `  M )  e.  NN0
1211nn0rei 10192 . . 3  |-  ( # `  M )  e.  RR
1312a1i 11 . 2  |-  ( ph  ->  ( # `  M
)  e.  RR )
14 2nn 10093 . . . . 5  |-  2  e.  NN
15 prmrec.2 . . . . . 6  |-  ( ph  ->  K  e.  NN )
1615nnnn0d 10234 . . . . 5  |-  ( ph  ->  K  e.  NN0 )
17 nnexpcl 11353 . . . . 5  |-  ( ( 2  e.  NN  /\  K  e.  NN0 )  -> 
( 2 ^ K
)  e.  NN )
1814, 16, 17sylancr 645 . . . 4  |-  ( ph  ->  ( 2 ^ K
)  e.  NN )
1918nnred 9975 . . 3  |-  ( ph  ->  ( 2 ^ K
)  e.  RR )
201nnrpd 10607 . . . . 5  |-  ( ph  ->  N  e.  RR+ )
2120rpsqrcld 12173 . . . 4  |-  ( ph  ->  ( sqr `  N
)  e.  RR+ )
2221rpred 10608 . . 3  |-  ( ph  ->  ( sqr `  N
)  e.  RR )
2319, 22remulcld 9076 . 2  |-  ( ph  ->  ( ( 2 ^ K )  x.  ( sqr `  N ) )  e.  RR )
242recnd 9074 . . . . . 6  |-  ( ph  ->  N  e.  CC )
25242halvesd 10173 . . . . 5  |-  ( ph  ->  ( ( N  / 
2 )  +  ( N  /  2 ) )  =  N )
267a1i 11 . . . . . . . . 9  |-  ( ph  ->  M  C_  ( 1 ... N ) )
2715peano2nnd 9977 . . . . . . . . . . . . 13  |-  ( ph  ->  ( K  +  1 )  e.  NN )
28 elfzuz 11015 . . . . . . . . . . . . 13  |-  ( k  e.  ( ( K  +  1 ) ... N )  ->  k  e.  ( ZZ>= `  ( K  +  1 ) ) )
29 nnuz 10481 . . . . . . . . . . . . . 14  |-  NN  =  ( ZZ>= `  1 )
3029uztrn2 10463 . . . . . . . . . . . . 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 2468 . . . . . . . . . . . . . . . . 17  |-  ( p  =  k  ->  (
p  e.  Prime  <->  k  e.  Prime ) )
33 breq1 4179 . . . . . . . . . . . . . . . . 17  |-  ( p  =  k  ->  (
p  ||  n  <->  k  ||  n ) )
3432, 33anbi12d 692 . . . . . . . . . . . . . . . 16  |-  ( p  =  k  ->  (
( p  e.  Prime  /\  p  ||  n )  <-> 
( k  e.  Prime  /\  k  ||  n ) ) )
3534rabbidv 2912 . . . . . . . . . . . . . . 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 6069 . . . . . . . . . . . . . . . 16  |-  ( 1 ... N )  e. 
_V
3837rabex 4318 . . . . . . . . . . . . . . 15  |-  { n  e.  ( 1 ... N
)  |  ( k  e.  Prime  /\  k  ||  n ) }  e.  _V
3935, 36, 38fvmpt 5769 . . . . . . . . . . . . . 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 3392 . . . . . . . . . . . . 13  |-  { n  e.  ( 1 ... N
)  |  ( k  e.  Prime  /\  k  ||  n ) }  C_  ( 1 ... N
)
4240, 41syl6eqss 3362 . . . . . . . . . . . 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 2753 . . . . . . . . . 10  |-  ( ph  ->  A. k  e.  ( ( K  +  1 ) ... N ) ( W `  k
)  C_  ( 1 ... N ) )
45 iunss 4096 . . . . . . . . . 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 3487 . . . . . . . 8  |-  ( ph  ->  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) )  C_  ( 1 ... N ) )
48 breq1 4179 . . . . . . . . . . . . . . . . . 18  |-  ( p  =  q  ->  (
p  ||  n  <->  q  ||  n ) )
4948notbid 286 . . . . . . . . . . . . . . . . 17  |-  ( p  =  q  ->  ( -.  p  ||  n  <->  -.  q  ||  n ) )
5049cbvralv 2896 . . . . . . . . . . . . . . . 16  |-  ( A. p  e.  ( Prime  \  ( 1 ... K
) )  -.  p  ||  n  <->  A. q  e.  ( Prime  \  ( 1 ... K ) )  -.  q  ||  n
)
51 breq2 4180 . . . . . . . . . . . . . . . . . 18  |-  ( n  =  x  ->  (
q  ||  n  <->  q  ||  x ) )
5251notbid 286 . . . . . . . . . . . . . . . . 17  |-  ( n  =  x  ->  ( -.  q  ||  n  <->  -.  q  ||  x ) )
5352ralbidv 2690 . . . . . . . . . . . . . . . 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 3058 . . . . . . . . . . . . . 14  |-  ( x  e.  M  <->  ( x  e.  ( 1 ... N
)  /\  A. q  e.  ( Prime  \  (
1 ... K ) )  -.  q  ||  x
) )
56 elun1 3478 . . . . . . . . . . . . . 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 2683 . . . . . . . . . . . 12  |-  ( E. q  e.  ( Prime  \  ( 1 ... K ) ) q 
||  x  <->  -.  A. q  e.  ( Prime  \  (
1 ... K ) )  -.  q  ||  x
)
61 eldifn 3434 . . . . . . . . . . . . . . . . . . . . 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 3433 . . . . . . . . . . . . . . . . . . . . . . . 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 13041 . . . . . . . . . . . . . . . . . . . . . . 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 2498 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  e.  (
ZZ>= `  1 ) )
6815nnzd 10334 . . . . . . . . . . . . . . . . . . . . . 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 11011 . . . . . . . . . . . . . . . . . . . . 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 9975 . . . . . . . . . . . . . . . . . . . . 21  |-  ( ph  ->  K  e.  RR )
7473ad2antrr 707 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  K  e.  RR )
7566nnred 9975 . . . . . . . . . . . . . . . . . . . 20  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  e.  RR )
7674, 75ltnled 9180 . . . . . . . . . . . . . . . . . . 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 13042 . . . . . . . . . . . . . . . . . . . 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 10285 . . . . . . . . . . . . . . . . . . 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 11040 . . . . . . . . . . . . . . . . . . . 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 9975 . . . . . . . . . . . . . . . . . 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 12854 . . . . . . . . . . . . . . . . . . . 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 11021 . . . . . . . . . . . . . . . . . . 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 9187 . . . . . . . . . . . . . . . . 17  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  q  <_  N
)
9468peano2zd 10338 . . . . . . . . . . . . . . . . . . 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 10334 . . . . . . . . . . . . . . . . . . 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 11009 . . . . . . . . . . . . . . . . . 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 3056 . . . . . . . . . . . . . . . . . 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 2468 . . . . . . . . . . . . . . . . . . . . 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 2912 . . . . . . . . . . . . . . . . . . 19  |-  ( p  =  q  ->  { n  e.  ( 1 ... N
)  |  ( p  e.  Prime  /\  p  ||  n ) }  =  { n  e.  (
1 ... N )  |  ( q  e.  Prime  /\  q  ||  n ) } )
10937rabex 4318 . . . . . . . . . . . . . . . . . . 19  |-  { n  e.  ( 1 ... N
)  |  ( q  e.  Prime  /\  q  ||  n ) }  e.  _V
110108, 36, 109fvmpt 5769 . . . . . . . . . . . . . . . . . 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 2485 . . . . . . . . . . . . . . . 16  |-  ( ( ( ph  /\  x  e.  ( 1 ... N
) )  /\  (
q  e.  ( Prime  \  ( 1 ... K ) )  /\  q  ||  x ) )  ->  x  e.  ( W `  q ) )
113 fveq2 5691 . . . . . . . . . . . . . . . . . 18  |-  ( k  =  q  ->  ( W `  k )  =  ( W `  q ) )
114113eleq2d 2475 . . . . . . . . . . . . . . . . 17  |-  ( k  =  q  ->  (
x  e.  ( W `
 k )  <->  x  e.  ( W `  q ) ) )
115114rspcev 3016 . . . . . . . . . . . . . . . 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 4061 . . . . . . . . . . . . . . 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 3479 . . . . . . . . . . . . . 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 2795 . . . . . . . . . . . 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 3318 . . . . . . . 8  |-  ( ph  ->  ( 1 ... N
)  C_  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) ) )
12647, 125eqssd 3329 . . . . . . 7  |-  ( ph  ->  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) )  =  ( 1 ... N ) )
127126fveq2d 5695 . . . . . 6  |-  ( ph  ->  ( # `  ( M  u.  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) )  =  ( # `  (
1 ... N ) ) )
1281nnnn0d 10234 . . . . . . 7  |-  ( ph  ->  N  e.  NN0 )
129 hashfz1 11589 . . . . . . 7  |-  ( N  e.  NN0  ->  ( # `  ( 1 ... N
) )  =  N )
130128, 129syl 16 . . . . . 6  |-  ( ph  ->  ( # `  (
1 ... N ) )  =  N )
131127, 130eqtr2d 2441 . . . . 5  |-  ( ph  ->  N  =  ( # `  ( M  u.  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) ) ) )
1329a1i 11 . . . . . 6  |-  ( ph  ->  M  e.  Fin )
133 ssfi 7292 . . . . . . 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 3596 . . . . . . . . . . . . . . . . . 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 3494 . . . . . . . . . . . . . . . . . . . 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 9901 . . . . . . . . . . . . . . . . . . . . . 22  |-  ( ph  ->  K  <  ( K  +  1 ) )
142 fzdisj 11038 . . . . . . . . . . . . . . . . . . . . . 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 2475 . . . . . . . . . . . . . . . . . . 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 3295 . . . . . . . . . . . . . . . 16  |-  ( ( ( ph  /\  x  e.  M )  /\  (
k  e.  ( ( K  +  1 ) ... N )  /\  k  e.  Prime ) )  ->  k  e.  ( Prime  \  ( 1 ... K ) ) )
149 breq2 4180 . . . . . . . . . . . . . . . . . . . . 21  |-  ( n  =  x  ->  (
p  ||  n  <->  p  ||  x
) )
150149notbid 286 . . . . . . . . . . . . . . . . . . . 20  |-  ( n  =  x  ->  ( -.  p  ||  n  <->  -.  p  ||  x ) )
151150ralbidv 2690 . . . . . . . . . . . . . . . . . . 19  |-  ( n  =  x  ->  ( A. p  e.  ( Prime  \  ( 1 ... K ) )  -.  p  ||  n  <->  A. p  e.  ( Prime  \  (
1 ... K ) )  -.  p  ||  x
) )
152151, 5elrab2 3058 . . . . . . . . . . . . . . . . . 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 4179 . . . . . . . . . . . . . . . . . 18  |-  ( p  =  k  ->  (
p  ||  x  <->  k  ||  x ) )
156155notbid 286 . . . . . . . . . . . . . . . . 17  |-  ( p  =  k  ->  ( -.  p  ||  x  <->  -.  k  ||  x ) )
157156rspcv 3012 . . . . . . . . . . . . . . . 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 2475 . . . . . . . . . . . . . 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 4180 . . . . . . . . . . . . . . . . 17  |-  ( n  =  x  ->  (
k  ||  n  <->  k  ||  x ) )
166165anbi2d 685 . . . . . . . . . . . . . . . 16  |-  ( n  =  x  ->  (
( k  e.  Prime  /\  k  ||  n )  <-> 
( k  e.  Prime  /\  k  ||  x ) ) )
167166elrab 3056 . . . . . . . . . . . . . . 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 2773 . . . . . . . . . . 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 3494 . . . . . . . 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 3626 . . . . . 6  |-  ( ph  ->  ( M  i^i  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k ) )  =  (/) )
179 hashun 11615 . . . . . 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 2444 . . . 4  |-  ( ph  ->  ( ( N  / 
2 )  +  ( N  /  2 ) )  =  ( (
# `  M )  +  ( # `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) ) ) )
182 hashcl 11598 . . . . . . 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 10235 . . . . 5  |-  ( ph  ->  ( # `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) )  e.  RR )
185 fzfid 11271 . . . . . . . 8  |-  ( ph  ->  ( ( K  + 
1 ) ... N
)  e.  Fin )
18627, 30sylan 458 . . . . . . . . . 10  |-  ( (
ph  /\  k  e.  ( ZZ>= `  ( K  +  1 ) ) )  ->  k  e.  NN )
187 nnrecre 9996 . . . . . . . . . . 11  |-  ( k  e.  NN  ->  (
1  /  k )  e.  RR )
188 0re 9051 . . . . . . . . . . 11  |-  0  e.  RR
189 ifcl 3739 . . . . . . . . . . 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 12487 . . . . . . 7  |-  ( ph  -> 
sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 )  e.  RR )
1942, 193remulcld 9076 . . . . . 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 13246 . . . . . . 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 10459 . . . . . . . . . 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 10289 . . . . . . . . . 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 11031 . . . . . . . . . 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 10041 . . . . . . . . . 10  |-  0  <_  0
20724mul01d 9225 . . . . . . . . . 10  |-  ( ph  ->  ( N  x.  0 )  =  0 )
208206, 207syl5breqr 4212 . . . . . . . . 9  |-  ( ph  ->  0  <_  ( N  x.  0 ) )
209 iuneq1 4070 . . . . . . . . . . . . 13  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k )  =  U_ k  e.  (/)  ( W `
 k ) )
210 0iun 4112 . . . . . . . . . . . . 13  |-  U_ k  e.  (/)  ( W `  k )  =  (/)
211209, 210syl6eq 2456 . . . . . . . . . . . 12  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k )  =  (/) )
212211fveq2d 5695 . . . . . . . . . . 11  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  ( # `  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) )  =  (
# `  (/) ) )
213 hash0 11605 . . . . . . . . . . 11  |-  ( # `  (/) )  =  0
214212, 213syl6eq 2456 . . . . . . . . . 10  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  ( # `  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) )  =  0 )
215 sumeq1 12442 . . . . . . . . . . . 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 12474 . . . . . . . . . . . 12  |-  sum_ k  e.  (/)  if ( k  e.  Prime ,  ( 1  /  k ) ,  0 )  =  0
217215, 216syl6eq 2456 . . . . . . . . . . 11  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  sum_ k  e.  ( ( K  + 
1 ) ... N
) if ( k  e.  Prime ,  ( 1  /  k ) ,  0 )  =  0 )
218217oveq2d 6060 . . . . . . . . . 10  |-  ( ( ( K  +  1 ) ... N )  =  (/)  ->  ( N  x.  sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 ) )  =  ( N  x.  0 ) )
219214, 218breq12d 4189 . . . . . . . . 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 10467 . . . . . . . 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 2408 . . . . . . . . . 10  |-  ( ZZ>= `  ( K  +  1
) )  =  (
ZZ>= `  ( K  + 
1 ) )
226 eleq1 2468 . . . . . . . . . . . . 13  |-  ( n  =  k  ->  (
n  e.  Prime  <->  k  e.  Prime ) )
227 oveq2 6052 . . . . . . . . . . . . 13  |-  ( n  =  k  ->  (
1  /  n )  =  ( 1  / 
k ) )
228 eqidd 2409 . . . . . . . . . . . . 13  |-  ( n  =  k  ->  0  =  0 )
229226, 227, 228ifbieq12d 3725 . . . . . . . . . . . 12  |-  ( n  =  k  ->  if ( n  e.  Prime ,  ( 1  /  n
) ,  0 )  =  if ( k  e.  Prime ,  ( 1  /  k ) ,  0 ) )
230 ovex 6069 . . . . . . . . . . . . 13  |-  ( 1  /  k )  e. 
_V
231 c0ex 9045 . . . . . . . . . . . . 13  |-  0  e.  _V
232230, 231ifex 3761 . . . . . . . . . . . 12  |-  if ( k  e.  Prime ,  ( 1  /  k ) ,  0 )  e. 
_V
233229, 195, 232fvmpt 5769 . . . . . . . . . . 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 9074 . . . . . . . . . . . . . 14  |-  ( k  e.  NN  ->  if ( k  e.  Prime ,  ( 1  /  k
) ,  0 )  e.  CC )
236233, 235eqeltrd 2482 . . . . . . . . . . . . 13  |-  ( k  e.  NN  ->  ( F `  k )  e.  CC )
237236adantl 453 . . . . . . . . . . . 12  |-  ( (
ph  /\  k  e.  NN )  ->  ( F `
 k )  e.  CC )
23829, 27, 237iserex 12409 . . . . . . . . . . 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 12508 . . . . . . . . 9  |-  ( ph  -> 
sum_ k  e.  (
ZZ>= `  ( K  + 
1 ) ) if ( k  e.  Prime ,  ( 1  /  k
) ,  0 )  e.  RR )
241 1re 9050 . . . . . . . . . . 11  |-  1  e.  RR
242241rehalfcli 10176 . . . . . . . . . 10  |-  ( 1  /  2 )  e.  RR
243242a1i 11 . . . . . . . . 9  |-  ( ph  ->  ( 1  /  2
)  e.  RR )
244 fzssuz 11053 . . . . . . . . . . 11  |-  ( ( K  +  1 ) ... N )  C_  ( ZZ>= `  ( K  +  1 ) )
245244a1i 11 . . . . . . . . . 10  |-  ( ph  ->  ( ( K  + 
1 ) ... N
)  C_  ( ZZ>= `  ( K  +  1
) ) )
246 nnrp 10581 . . . . . . . . . . . . . 14  |-  ( k  e.  NN  ->  k  e.  RR+ )
247246rpreccld 10618 . . . . . . . . . . . . 13  |-  ( k  e.  NN  ->  (
1  /  k )  e.  RR+ )
248247rpge0d 10612 . . . . . . . . . . . 12  |-  ( k  e.  NN  ->  0  <_  ( 1  /  k
) )
249 breq2 4180 . . . . . . . . . . . . 13  |-  ( ( 1  /  k )  =  if ( k  e.  Prime ,  ( 1  /  k ) ,  0 )  ->  (
0  <_  ( 1  /  k )  <->  0  <_  if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) ) )
250 breq2 4180 . . . . . . . . . . . . 13  |-  ( 0  =  if ( k  e.  Prime ,  ( 1  /  k ) ,  0 )  ->  (
0  <_  0  <->  0  <_  if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) ) )
251249, 250ifboth 3734 . . . . . . . . . . . 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 12584 . . . . . . . . 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 9188 . . . . . . . 8  |-  ( ph  -> 
sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e. 
Prime ,  ( 1  /  k ) ,  0 )  <  (
1  /  2 ) )
2561nngt0d 10003 . . . . . . . . 9  |-  ( ph  ->  0  <  N )
257 ltmul2 9821 . . . . . . . . 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 10030 . . . . . . . . 9  |-  2  e.  CC
261 2ne0 10043 . . . . . . . . 9  |-  2  =/=  0
262 divrec 9654 . . . . . . . . 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 4202 . . . . . 6  |-  ( ph  ->  ( N  x.  sum_ k  e.  ( ( K  +  1 ) ... N ) if ( k  e.  Prime ,  ( 1  /  k
) ,  0 ) )  <  ( N  /  2 ) )
266184, 194, 3, 224, 265lelttrd 9188 . . . . 5  |-  ( ph  ->  ( # `  U_ k  e.  ( ( K  + 
1 ) ... N
) ( W `  k ) )  < 
( N  /  2
) )
267184, 3, 13, 266ltadd2dd 9189 . . . 4  |-  ( ph  ->  ( ( # `  M
)  +  ( # `  U_ k  e.  ( ( K  +  1 ) ... N ) ( W `  k
) ) )  < 
( ( # `  M
)  +  ( N  /  2 ) ) )
268181, 267eqbrtrd 4196 . . 3  |-  ( ph  ->  ( ( N  / 
2 )  +  ( N  /  2 ) )  <  ( (
# `  M )  +  ( N  / 
2 ) ) )
2693, 13, 3ltadd1d 9579 . . 3  |-  ( ph  ->  ( ( N  / 
2 )  <  ( # `
 M )  <->  ( ( N  /  2 )  +  ( N  /  2
) )  <  (
( # `  M )  +  ( N  / 
2 ) ) ) )
270268, 269mpbird 224 . 2  |-  ( ph  ->  ( N  /  2
)  <  ( # `  M
) )
271 oveq1 6051 . . . . . . . 8  |-  ( k  =  r  ->  (
k ^ 2 )  =  ( r ^
2 ) )
272271breq1d 4186 . . . . . . 7  |-  ( k  =  r  ->  (
( k ^ 2 )  ||  x  <->  ( r ^ 2 )  ||  x ) )
273272cbvrabv 2919 . . . . . 6  |-  { k  e.  NN  |  ( k ^ 2 ) 
||  x }  =  { r  e.  NN  |  ( r ^
2 )  ||  x }
274 breq2 4180 . . . . . . 7  |-  ( x  =  n  ->  (
( r ^ 2 )  ||  x  <->  ( r ^ 2 )  ||  n ) )
275274rabbidv 2912 . . . . . 6  |-  ( x  =  n  ->  { r  e.  NN  |  ( r ^ 2 ) 
||  x }  =  { r  e.  NN  |  ( r ^
2 )  ||  n } )
276273, 275syl5eq 2452 . . . . 5  |-  ( x  =  n  ->  { k  e.  NN  |  ( k ^ 2 ) 
||  x }  =  { r  e.  NN  |  ( r ^
2 )  ||  n } )
277276supeq1d 7413 . . . 4  |-  ( x  =  n  ->  sup ( { k  e.  NN  |  ( k ^
2 )  ||  x } ,  RR ,  <  )  =  sup ( { r  e.  NN  |  ( r ^
2 )  ||  n } ,  RR ,  <  ) )
278277cbvmptv 4264 . . 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 13245 . 2  |-  ( ph  ->  ( # `  M
)  <_  ( (
2 ^ K )  x.  ( sqr `  N
) ) )
2803, 13, 23, 270, 279ltletrd 9190 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 2571   A.wral 2670   E.wrex 2671   {crab 2674    \ cdif 3281    u. cun 3282    i^i cin 3283    C_ wss 3284   (/)c0 3592   ifcif 3703   U_ciun 4057   class class class wbr 4176    e. cmpt 4230   dom cdm 4841   ` cfv 5417  (class class class)co 6044   Fincfn 7072   supcsup 7407   CCcc 8948   RRcr 8949   0cc0 8950   1c1 8951    + caddc 8953    x. cmul 8955    < clt 9080    <_ cle 9081    / cdiv 9637   NNcn 9960   2c2 10009   NN0cn0 10181   ZZcz 10242   ZZ>=cuz 10448   ...cfz 11003    seq cseq 11282   ^cexp 11341   #chash 11577   sqrcsqr 11997    ~~> cli 12237   sum_csu 12438    || cdivides 12811   Primecprime 13038
This theorem is referenced by:  prmreclem6  13248
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 2389  ax-rep 4284  ax-sep 4294  ax-nul 4302  ax-pow 4341  ax-pr 4367  ax-un 4664  ax-inf2 7556  ax-cnex 9006  ax-resscn 9007  ax-1cn 9008  ax-icn 9009  ax-addcl 9010  ax-addrcl 9011  ax-mulcl 9012  ax-mulrcl 9013  ax-mulcom 9014  ax-addass 9015  ax-mulass 9016  ax-distr 9017  ax-i2m1 9018  ax-1ne0 9019  ax-1rid 9020  ax-rnegex 9021  ax-rrecex 9022  ax-cnre 9023  ax-pre-lttri 9024  ax-pre-lttrn 9025  ax-pre-ltadd 9026  ax-pre-mulgt0 9027  ax-pre-sup 9028
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 2262  df-mo 2263  df-clab 2395  df-cleq 2401  df-clel 2404  df-nfc 2533  df-ne 2573  df-nel 2574  df-ral 2675  df-rex 2676  df-reu 2677  df-rmo 2678  df-rab 2679  df-v 2922  df-sbc 3126  df-csb 3216  df-dif 3287  df-un 3289  df-in 3291  df-ss 3298  df-pss 3300  df-nul 3593  df-if 3704  df-pw 3765  df-sn 3784  df-pr 3785  df-tp 3786  df-op 3787  df-uni 3980  df-int 4015  df-iun 4059  df-br 4177  df-opab 4231  df-mpt 4232  df-tr 4267  df-eprel 4458  df-id 4462  df-po 4467  df-so 4468  df-fr 4505  df-se 4506  df-we 4507  df-ord 4548  df-on 4549  df-lim 4550  df-suc 4551  df-om 4809  df-xp 4847  df-rel 4848  df-cnv 4849  df-co 4850  df-dm 4851  df-rn 4852  df-res 4853  df-ima 4854  df-iota 5381  df-fun 5419  df-fn 5420  df-f 5421  df-f1 5422  df-fo 5423  df-f1o 5424  df-fv 5425  df-isom 5426  df-ov 6047  df-oprab 6048  df-mpt2 6049  df-1st 6312  df-2nd 6313  df-riota 6512  df-recs 6596  df-rdg 6631  df-1o 6687  df-2o 6688  df-oadd 6691  df-er 6868  df-map 6983  df-pm 6984  df-en 7073  df-dom 7074  df-sdom 7075  df-fin 7076  df-sup 7408  df-oi 7439  df-card 7786  df-cda 8008  df-pnf 9082  df-mnf 9083  df-xr 9084  df-ltxr 9085  df-le 9086  df-sub 9253  df-neg 9254  df-div 9638  df-nn 9961  df-2 10018  df-3 10019  df-n0 10182  df-z 10243  df-uz 10449  df-q 10535  df-rp 10573  df-fz 11004  df-fzo 11095  df-fl 11161  df-mod 11210  df-seq 11283  df-exp 11342  df-hash 11578  df-cj 11863  df-re 11864  df-im 11865  df-sqr 11999  df-abs 12000  df-clim 12241  df-rlim 12242  df-sum 12439  df-dvds 12812  df-gcd 12966  df-prm 13039  df-pc 13170
  Copyright terms: Public domain W3C validator