pcfac - Intuitionistic Logic Explorer

	Intuitionistic Logic Explorer		< Previous Next > Nearby theorems
Mirrors > Home > ILE Home > Th. List > pcfac		Unicode version

Theorem pcfac 13107

Description: Calculate the prime count of a factorial. (Contributed by Mario Carneiro, 11-Mar-2014.) (Revised by Mario Carneiro, 21-May-2014.)

**Assertion**
Ref	Expression
pcfac	$/\$ $/\$

Distinct variable groups:

Proof of Theorem pcfac Dummy variables

are mutually distinct and distinct from all other variables.

Step	Hyp	Ref	Expression
1		fveq2 5690	. . . . . . . 8
2		fveq2 5690	. . . . . . . . . 10
3	2	oveq2d 6091	. . . . . . . . 9
4		fvoveq1 6098	. . . . . . . . . 10
5	4	sumeq2sdv 12114	. . . . . . . . 9
6	3, 5	eqeq12d 2253	. . . . . . . 8
7	1, 6	raleqbidv 2765	. . . . . . 7
8	7	imbi2d 230	. . . . . 6
9		fveq2 5690	. . . . . . . 8
10		fveq2 5690	. . . . . . . . . 10
11	10	oveq2d 6091	. . . . . . . . 9
12		fvoveq1 6098	. . . . . . . . . 10
13	12	sumeq2sdv 12114	. . . . . . . . 9
14	11, 13	eqeq12d 2253	. . . . . . . 8
15	9, 14	raleqbidv 2765	. . . . . . 7
16	15	imbi2d 230	. . . . . 6
17		fveq2 5690	. . . . . . . 8
18		fveq2 5690	. . . . . . . . . 10
19	18	oveq2d 6091	. . . . . . . . 9
20		fvoveq1 6098	. . . . . . . . . 10
21	20	sumeq2sdv 12114	. . . . . . . . 9
22	19, 21	eqeq12d 2253	. . . . . . . 8
23	17, 22	raleqbidv 2765	. . . . . . 7
24	23	imbi2d 230	. . . . . 6
25		fveq2 5690	. . . . . . . 8
26		fveq2 5690	. . . . . . . . . 10
27	26	oveq2d 6091	. . . . . . . . 9
28		fvoveq1 6098	. . . . . . . . . 10
29	28	sumeq2sdv 12114	. . . . . . . . 9
30	27, 29	eqeq12d 2253	. . . . . . . 8
31	25, 30	raleqbidv 2765	. . . . . . 7
32	31	imbi2d 230	. . . . . 6
33		1zzd 9650	. . . . . . . . . 10 $/\$
34		eluzelz 9910	. . . . . . . . . . 11
35	34	adantl 277	. . . . . . . . . 10 $/\$
36	33, 35	fzfigd 10846	. . . . . . . . 9 $/\$
37		isumz 12134	. . . . . . . . . 10 $/\$ $/\$ DECID $\/$
38	37	olcs 748	. . . . . . . . 9
39	36, 38	syl 14	. . . . . . . 8 $/\$
40		0nn0 9557	. . . . . . . . . 10
41		elfznn 10438	. . . . . . . . . . . . 13
42	41	nnnn0d 9599	. . . . . . . . . . . 12
43		nn0uz 9936	. . . . . . . . . . . 12
44	42, 43	eleqtrdi 2331	. . . . . . . . . . 11
45	44	adantl 277	. . . . . . . . . 10 $/\$ $/\$
46		simpll 531	. . . . . . . . . 10 $/\$ $/\$
47		pcfaclem 13106	. . . . . . . . . 10 $/\$ $/\$
48	40, 45, 46, 47	mp3an2i 1383	. . . . . . . . 9 $/\$ $/\$
49	48	sumeq2dv 12112	. . . . . . . 8 $/\$
50		fac0 11144	. . . . . . . . . . 11
51	50	oveq2i 6086	. . . . . . . . . 10
52		pc1 13062	. . . . . . . . . 10
53	51, 52	eqtrid 2283	. . . . . . . . 9
54	53	adantr 276	. . . . . . . 8 $/\$
55	39, 49, 54	3eqtr4rd 2282	. . . . . . 7 $/\$
56	55	ralrimiva 2623	. . . . . 6
57		nn0z 9643	. . . . . . . . . . . 12
58	57	adantr 276	. . . . . . . . . . 11 $/\$
59		uzid 9915	. . . . . . . . . . 11
60		peano2uz 9962	. . . . . . . . . . 11
61	58, 59, 60	3syl 17	. . . . . . . . . 10 $/\$
62		uzss 9922	. . . . . . . . . 10
63		ssralv 3312	. . . . . . . . . 10
64	61, 62, 63	3syl 17	. . . . . . . . 9 $/\$
65		oveq1 6082	. . . . . . . . . . 11
66		simpll 531	. . . . . . . . . . . . . . 15 $/\$ $/\$
67		facp1 11146	. . . . . . . . . . . . . . 15
68	66, 67	syl 14	. . . . . . . . . . . . . 14 $/\$ $/\$
69	68	oveq2d 6091	. . . . . . . . . . . . 13 $/\$ $/\$
70		simplr 533	. . . . . . . . . . . . . 14 $/\$ $/\$
71		faccl 11151	. . . . . . . . . . . . . . 15
72		nnz 9642	. . . . . . . . . . . . . . . 16
73		nnne0 9311	. . . . . . . . . . . . . . . 16
74	72, 73	jca 306	. . . . . . . . . . . . . . 15 $/\$
75	66, 71, 74	3syl 17	. . . . . . . . . . . . . 14 $/\$ $/\$ $/\$
76		nn0p1nn 9581	. . . . . . . . . . . . . . 15
77		nnz 9642	. . . . . . . . . . . . . . . 16
78		nnne0 9311	. . . . . . . . . . . . . . . 16
79	77, 78	jca 306	. . . . . . . . . . . . . . 15 $/\$
80	66, 76, 79	3syl 17	. . . . . . . . . . . . . 14 $/\$ $/\$ $/\$
81		pcmul 13058	. . . . . . . . . . . . . 14 $/\$ $/\$ $/\$ $/\$
82	70, 75, 80, 81	syl3anc 1278	. . . . . . . . . . . . 13 $/\$ $/\$
83	69, 82	eqtr2d 2272	. . . . . . . . . . . 12 $/\$ $/\$
84	66	adantr 276	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$ $/\$
85	84	nn0zd 9745	. . . . . . . . . . . . . . . . 17 $/\$ $/\$ $/\$
86		prmnn 12866	. . . . . . . . . . . . . . . . . . 19
87	86	ad2antlr 493	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$
88		nnexpcl 10967	. . . . . . . . . . . . . . . . . 18 $/\$
89	87, 42, 88	syl2an 289	. . . . . . . . . . . . . . . . 17 $/\$ $/\$ $/\$
90		fldivp1 13105	. . . . . . . . . . . . . . . . 17 $/\$
91	85, 89, 90	syl2anc 415	. . . . . . . . . . . . . . . 16 $/\$ $/\$ $/\$
92		elfzuz 10403	. . . . . . . . . . . . . . . . . . 19
93	66, 76	syl 14	. . . . . . . . . . . . . . . . . . . . 21 $/\$ $/\$
94	70, 93	pccld 13057	. . . . . . . . . . . . . . . . . . . 20 $/\$ $/\$
95	94	nn0zd 9745	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$
96		elfz5 10399	. . . . . . . . . . . . . . . . . . 19 $/\$
97	92, 95, 96	syl2anr 290	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$ $/\$
98		simpllr 540	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$ $/\$
99	84, 76	syl 14	. . . . . . . . . . . . . . . . . . . 20 $/\$ $/\$ $/\$
100	99	nnzd 9746	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$ $/\$
101	42	adantl 277	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$ $/\$
102		pcdvdsb 13077	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$
103	98, 100, 101, 102	syl3anc 1278	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$ $/\$
104	97, 103	bitr2d 189	. . . . . . . . . . . . . . . . 17 $/\$ $/\$ $/\$
105	104	ifbid 3659	. . . . . . . . . . . . . . . 16 $/\$ $/\$ $/\$
106	91, 105	eqtrd 2271	. . . . . . . . . . . . . . 15 $/\$ $/\$ $/\$
107	106	sumeq2dv 12112	. . . . . . . . . . . . . 14 $/\$ $/\$
108		1zzd 9650	. . . . . . . . . . . . . . . 16 $/\$ $/\$
109		eluzelz 9910	. . . . . . . . . . . . . . . . 17
110	109	adantl 277	. . . . . . . . . . . . . . . 16 $/\$ $/\$
111	108, 110	fzfigd 10846	. . . . . . . . . . . . . . 15 $/\$ $/\$
112		znq 10003	. . . . . . . . . . . . . . . . . 18 $/\$
113	100, 89, 112	syl2anc 415	. . . . . . . . . . . . . . . . 17 $/\$ $/\$ $/\$
114	113	flqcld 10690	. . . . . . . . . . . . . . . 16 $/\$ $/\$ $/\$
115	114	zcnd 9748	. . . . . . . . . . . . . . 15 $/\$ $/\$ $/\$
116		znq 10003	. . . . . . . . . . . . . . . . . 18 $/\$
117	85, 89, 116	syl2anc 415	. . . . . . . . . . . . . . . . 17 $/\$ $/\$ $/\$
118	117	flqcld 10690	. . . . . . . . . . . . . . . 16 $/\$ $/\$ $/\$
119	118	zcnd 9748	. . . . . . . . . . . . . . 15 $/\$ $/\$ $/\$
120	111, 115, 119	fsumsub 12197	. . . . . . . . . . . . . 14 $/\$ $/\$
121	94	nn0red 9600	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$
122	66	nn0red 9600	. . . . . . . . . . . . . . . . . . . 20 $/\$ $/\$
123		peano2re 8452	. . . . . . . . . . . . . . . . . . . 20
124	122, 123	syl 14	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$
125	110	zred 9747	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$
126	93	nnzd 9746	. . . . . . . . . . . . . . . . . . . . 21 $/\$ $/\$
127		zdcle 9700	. . . . . . . . . . . . . . . . . . . . 21 $/\$ DECID
128	95, 126, 127	syl2anc 415	. . . . . . . . . . . . . . . . . . . 20 $/\$ $/\$ DECID
129		zletric 9667	. . . . . . . . . . . . . . . . . . . . . . 23 $/\$ $\/$
130	95, 126, 129	syl2anc 415	. . . . . . . . . . . . . . . . . . . . . 22 $/\$ $/\$ $\/$
131	130	ord 736	. . . . . . . . . . . . . . . . . . . . 21 $/\$ $/\$
132	93	nnnn0d 9599	. . . . . . . . . . . . . . . . . . . . . . 23 $/\$ $/\$
133		pcdvdsb 13077	. . . . . . . . . . . . . . . . . . . . . . 23 $/\$ $/\$
134	70, 126, 132, 133	syl3anc 1278	. . . . . . . . . . . . . . . . . . . . . 22 $/\$ $/\$
135	87, 132	nnexpcld 11111	. . . . . . . . . . . . . . . . . . . . . . . . 25 $/\$ $/\$
136	135	nnzd 9746	. . . . . . . . . . . . . . . . . . . . . . . 24 $/\$ $/\$
137		dvdsle 12589	. . . . . . . . . . . . . . . . . . . . . . . 24 $/\$
138	136, 93, 137	syl2anc 415	. . . . . . . . . . . . . . . . . . . . . . 23 $/\$ $/\$
139	135	nnred 9296	. . . . . . . . . . . . . . . . . . . . . . . 24 $/\$ $/\$
140	139, 124	lenltd 8434	. . . . . . . . . . . . . . . . . . . . . . 23 $/\$ $/\$
141	138, 140	sylibd 149	. . . . . . . . . . . . . . . . . . . . . 22 $/\$ $/\$
142	134, 141	sylbid 150	. . . . . . . . . . . . . . . . . . . . 21 $/\$ $/\$
143	131, 142	syld 45	. . . . . . . . . . . . . . . . . . . 20 $/\$ $/\$
144		prmuz2 12887	. . . . . . . . . . . . . . . . . . . . . 22
145	144	ad2antlr 493	. . . . . . . . . . . . . . . . . . . . 21 $/\$ $/\$
146		bernneq3 11078	. . . . . . . . . . . . . . . . . . . . 21 $/\$
147	145, 132, 146	syl2anc 415	. . . . . . . . . . . . . . . . . . . 20 $/\$ $/\$
148		condc 865	. . . . . . . . . . . . . . . . . . . 20 DECID
149	128, 143, 147, 148	syl3c 63	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$
150		eluzle 9913	. . . . . . . . . . . . . . . . . . . 20
151	150	adantl 277	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$
152	121, 124, 125, 149, 151	letrd 8440	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$
153		eluz 9914	. . . . . . . . . . . . . . . . . . 19 $/\$
154	95, 110, 153	syl2anc 415	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$
155	152, 154	mpbird 167	. . . . . . . . . . . . . . . . 17 $/\$ $/\$
156		fzss2 10448	. . . . . . . . . . . . . . . . 17
157	155, 156	syl 14	. . . . . . . . . . . . . . . 16 $/\$ $/\$
158		elfzelz 10407	. . . . . . . . . . . . . . . . . . 19
159	158	adantl 277	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$ $/\$
160		1zzd 9650	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$ $/\$
161	95	adantr 276	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$ $/\$
162		fzdcel 10423	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$ DECID
163	159, 160, 161, 162	syl3anc 1278	. . . . . . . . . . . . . . . . 17 $/\$ $/\$ $/\$ DECID
164	163	ralrimiva 2623	. . . . . . . . . . . . . . . 16 $/\$ $/\$ DECID
165		sumhashdc 13104	. . . . . . . . . . . . . . . 16 $/\$ $/\$ DECID ♯
166	111, 157, 164, 165	syl3anc 1278	. . . . . . . . . . . . . . 15 $/\$ $/\$ ♯
167		hashfz1 11200	. . . . . . . . . . . . . . . 16 ♯
168	94, 167	syl 14	. . . . . . . . . . . . . . 15 $/\$ $/\$ ♯
169	166, 168	eqtrd 2271	. . . . . . . . . . . . . 14 $/\$ $/\$
170	107, 120, 169	3eqtr3d 2279	. . . . . . . . . . . . 13 $/\$ $/\$
171	111, 115	fsumcl 12145	. . . . . . . . . . . . . 14 $/\$ $/\$
172	111, 119	fsumcl 12145	. . . . . . . . . . . . . 14 $/\$ $/\$
173	94	nn0cnd 9601	. . . . . . . . . . . . . 14 $/\$ $/\$
174	171, 172, 173	subaddd 8645	. . . . . . . . . . . . 13 $/\$ $/\$
175	170, 174	mpbid 147	. . . . . . . . . . . 12 $/\$ $/\$
176	83, 175	eqeq12d 2253	. . . . . . . . . . 11 $/\$ $/\$
177	65, 176	imbitrid 154	. . . . . . . . . 10 $/\$ $/\$
178	177	ralimdva 2617	. . . . . . . . 9 $/\$
179	64, 178	syld 45	. . . . . . . 8 $/\$
180	179	ex 115	. . . . . . 7
181	180	a2d 26	. . . . . 6
182	8, 16, 24, 32, 56, 181	nn0ind 9739	. . . . 5
183	182	imp 124	. . . 4 $/\$
184		oveq2 6083	. . . . . . 7
185	184	sumeq1d 12110	. . . . . 6
186	185	eqeq2d 2250	. . . . 5
187	186	rspcv 2925	. . . 4
188	183, 187	syl5 32	. . 3 $/\$
189	188	3impib 1232	. 2 $/\$ $/\$
190	189	3com12 1238	1 $/\$ $/\$

Colors of variables: wff set class

Syntax hints:

wn 3

wi 4 $/\$ wa 104

wb 105 $\/$ wo 720 DECID wdc 846 $/\$ w3a 1009

wceq 1402

wcel 2209

wne 2420

wral 2528

wss 3220

cif 3635 class class class wbr 4125

cfv 5372 (class class class)co 6075

cfn 7012

cr 8168

cc0 8169

c1 8170

caddc 8172

cmul 8174

clt 8350

cle 8351

cmin 8487

cdiv 8992

cn 9283

c2 9334

cn0 9542

cz 9623

cuz 9900

cq 9998

cfz 10390

cfl 10681

cexp 10953

cfa 11141 ♯chash 11192

csu 12097

cdvds 12532

cprime 12863

cpc 13041

This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-ia1 106 ax-ia2 107 ax-ia3 108 ax-in1 623 ax-in2 624 ax-io 721 ax-5 1500 ax-7 1501 ax-gen 1502 ax-ie1 1546 ax-ie2 1547 ax-8 1557 ax-10 1558 ax-11 1559 ax-i12 1560 ax-bndl 1562 ax-4 1563 ax-17 1579 ax-i9 1583 ax-ial 1587 ax-i5r 1588 ax-14 2212 ax-ext 2220 ax-coll 4241 ax-sep 4244 ax-nul 4254 ax-pow 4306 ax-pr 4341 ax-un 4573 ax-setind 4679 ax-iinf 4730 ax-cnex 8260 ax-resscn 8261 ax-1cn 8262 ax-1re 8263 ax-icn 8264 ax-addcl 8265 ax-addrcl 8266 ax-mulcl 8267 ax-mulrcl 8268 ax-addcom 8269 ax-mulcom 8270 ax-addass 8271 ax-mulass 8272 ax-distr 8273 ax-i2m1 8274 ax-0lt1 8275 ax-1rid 8276 ax-0id 8277 ax-rnegex 8278 ax-precex 8279 ax-cnre 8280 ax-pre-ltirr 8281 ax-pre-ltwlin 8282 ax-pre-lttrn 8283 ax-pre-apti 8284 ax-pre-ltadd 8285 ax-pre-mulgt0 8286 ax-pre-mulext 8287 ax-arch 8288 ax-caucvg 8289

This theorem depends on definitions: df-bi 117 df-stab 843 df-dc 847 df-3or 1010 df-3an 1011 df-tru 1405 df-fal 1408 df-nf 1514 df-sb 1816 df-eu 2089 df-mo 2090 df-clab 2225 df-cleq 2231 df-clel 2234 df-nfc 2381 df-ne 2421 df-nel 2516 df-ral 2533 df-rex 2534 df-reu 2535 df-rmo 2536 df-rab 2537 df-v 2823 df-sbc 3052 df-csb 3148 df-dif 3222 df-un 3224 df-in 3226 df-ss 3233 df-nul 3521 df-if 3636 df-pw 3687 df-sn 3711 df-pr 3712 df-op 3714 df-uni 3931 df-int 3966 df-iun 4009 df-br 4126 df-opab 4188 df-mpt 4189 df-tr 4225 df-id 4433 df-po 4436 df-iso 4437 df-iord 4506 df-on 4508 df-ilim 4509 df-suc 4511 df-iom 4733 df-xp 4775 df-rel 4776 df-cnv 4777 df-co 4778 df-dm 4779 df-rn 4780 df-res 4781 df-ima 4782 df-iota 5332 df-fun 5374 df-fn 5375 df-f 5376 df-f1 5377 df-fo 5378 df-f1o 5379 df-fv 5380 df-isom 5381 df-riota 6028 df-ov 6078 df-oprab 6079 df-mpo 6080 df-1st 6364 df-2nd 6365 df-recs 6566 df-irdg 6631 df-frec 6652 df-1o 6677 df-2o 6678 df-oadd 6681 df-er 6797 df-en 7013 df-dom 7014 df-fin 7015 df-sup 7314 df-inf 7315 df-pnf 8352 df-mnf 8353 df-xr 8354 df-ltxr 8355 df-le 8356 df-sub 8489 df-neg 8490 df-reap 8893 df-ap 8900 df-div 8993 df-inn 9284 df-2 9342 df-3 9343 df-4 9344 df-n0 9543 df-z 9624 df-uz 9901 df-q 9999 df-rp 10034 df-fz 10391 df-fzo 10528 df-fl 10683 df-mod 10738 df-seqfrec 10863 df-exp 10954 df-fac 11142 df-ihash 11193 df-cj 11585 df-re 11586 df-im 11587 df-rsqrt 11742 df-abs 11743 df-clim 12023 df-sumdc 12098 df-dvds 12533 df-gcd 12709 df-prm 12864 df-pc 13042

This theorem is referenced by: pcbc 13108

W3C validator