pcfac - Intuitionistic Logic Explorer

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

Theorem pcfac 12280

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 5486	. . . . . . . 8
2		fveq2 5486	. . . . . . . . . 10
3	2	oveq2d 5858	. . . . . . . . 9
4		fvoveq1 5865	. . . . . . . . . 10
5	4	sumeq2sdv 11311	. . . . . . . . 9
6	3, 5	eqeq12d 2180	. . . . . . . 8
7	1, 6	raleqbidv 2673	. . . . . . 7
8	7	imbi2d 229	. . . . . 6
9		fveq2 5486	. . . . . . . 8
10		fveq2 5486	. . . . . . . . . 10
11	10	oveq2d 5858	. . . . . . . . 9
12		fvoveq1 5865	. . . . . . . . . 10
13	12	sumeq2sdv 11311	. . . . . . . . 9
14	11, 13	eqeq12d 2180	. . . . . . . 8
15	9, 14	raleqbidv 2673	. . . . . . 7
16	15	imbi2d 229	. . . . . 6
17		fveq2 5486	. . . . . . . 8
18		fveq2 5486	. . . . . . . . . 10
19	18	oveq2d 5858	. . . . . . . . 9
20		fvoveq1 5865	. . . . . . . . . 10
21	20	sumeq2sdv 11311	. . . . . . . . 9
22	19, 21	eqeq12d 2180	. . . . . . . 8
23	17, 22	raleqbidv 2673	. . . . . . 7
24	23	imbi2d 229	. . . . . 6
25		fveq2 5486	. . . . . . . 8
26		fveq2 5486	. . . . . . . . . 10
27	26	oveq2d 5858	. . . . . . . . 9
28		fvoveq1 5865	. . . . . . . . . 10
29	28	sumeq2sdv 11311	. . . . . . . . 9
30	27, 29	eqeq12d 2180	. . . . . . . 8
31	25, 30	raleqbidv 2673	. . . . . . 7
32	31	imbi2d 229	. . . . . 6
33		1zzd 9218	. . . . . . . . . 10 $/\$
34		eluzelz 9475	. . . . . . . . . . 11
35	34	adantl 275	. . . . . . . . . 10 $/\$
36	33, 35	fzfigd 10366	. . . . . . . . 9 $/\$
37		isumz 11330	. . . . . . . . . 10 $/\$ $/\$ DECID $\/$
38	37	olcs 726	. . . . . . . . 9
39	36, 38	syl 14	. . . . . . . 8 $/\$
40		0nn0 9129	. . . . . . . . . 10
41		elfznn 9989	. . . . . . . . . . . . 13
42	41	nnnn0d 9167	. . . . . . . . . . . 12
43		nn0uz 9500	. . . . . . . . . . . 12
44	42, 43	eleqtrdi 2259	. . . . . . . . . . 11
45	44	adantl 275	. . . . . . . . . 10 $/\$ $/\$
46		simpll 519	. . . . . . . . . 10 $/\$ $/\$
47		pcfaclem 12279	. . . . . . . . . 10 $/\$ $/\$
48	40, 45, 46, 47	mp3an2i 1332	. . . . . . . . 9 $/\$ $/\$
49	48	sumeq2dv 11309	. . . . . . . 8 $/\$
50		fac0 10641	. . . . . . . . . . 11
51	50	oveq2i 5853	. . . . . . . . . 10
52		pc1 12237	. . . . . . . . . 10
53	51, 52	syl5eq 2211	. . . . . . . . 9
54	53	adantr 274	. . . . . . . 8 $/\$
55	39, 49, 54	3eqtr4rd 2209	. . . . . . 7 $/\$
56	55	ralrimiva 2539	. . . . . 6
57		nn0z 9211	. . . . . . . . . . . 12
58	57	adantr 274	. . . . . . . . . . 11 $/\$
59		uzid 9480	. . . . . . . . . . 11
60		peano2uz 9521	. . . . . . . . . . 11
61	58, 59, 60	3syl 17	. . . . . . . . . 10 $/\$
62		uzss 9486	. . . . . . . . . 10
63		ssralv 3206	. . . . . . . . . 10
64	61, 62, 63	3syl 17	. . . . . . . . 9 $/\$
65		oveq1 5849	. . . . . . . . . . 11
66		simpll 519	. . . . . . . . . . . . . . 15 $/\$ $/\$
67		facp1 10643	. . . . . . . . . . . . . . 15
68	66, 67	syl 14	. . . . . . . . . . . . . 14 $/\$ $/\$
69	68	oveq2d 5858	. . . . . . . . . . . . 13 $/\$ $/\$
70		simplr 520	. . . . . . . . . . . . . 14 $/\$ $/\$
71		faccl 10648	. . . . . . . . . . . . . . 15
72		nnz 9210	. . . . . . . . . . . . . . . 16
73		nnne0 8885	. . . . . . . . . . . . . . . 16
74	72, 73	jca 304	. . . . . . . . . . . . . . 15 $/\$
75	66, 71, 74	3syl 17	. . . . . . . . . . . . . 14 $/\$ $/\$ $/\$
76		nn0p1nn 9153	. . . . . . . . . . . . . . 15
77		nnz 9210	. . . . . . . . . . . . . . . 16
78		nnne0 8885	. . . . . . . . . . . . . . . 16
79	77, 78	jca 304	. . . . . . . . . . . . . . 15 $/\$
80	66, 76, 79	3syl 17	. . . . . . . . . . . . . 14 $/\$ $/\$ $/\$
81		pcmul 12233	. . . . . . . . . . . . . 14 $/\$ $/\$ $/\$ $/\$
82	70, 75, 80, 81	syl3anc 1228	. . . . . . . . . . . . 13 $/\$ $/\$
83	69, 82	eqtr2d 2199	. . . . . . . . . . . 12 $/\$ $/\$
84	66	adantr 274	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$ $/\$
85	84	nn0zd 9311	. . . . . . . . . . . . . . . . 17 $/\$ $/\$ $/\$
86		prmnn 12042	. . . . . . . . . . . . . . . . . . 19
87	86	ad2antlr 481	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$
88		nnexpcl 10468	. . . . . . . . . . . . . . . . . 18 $/\$
89	87, 42, 88	syl2an 287	. . . . . . . . . . . . . . . . 17 $/\$ $/\$ $/\$
90		fldivp1 12278	. . . . . . . . . . . . . . . . 17 $/\$
91	85, 89, 90	syl2anc 409	. . . . . . . . . . . . . . . 16 $/\$ $/\$ $/\$
92		elfzuz 9956	. . . . . . . . . . . . . . . . . . 19
93	66, 76	syl 14	. . . . . . . . . . . . . . . . . . . . 21 $/\$ $/\$
94	70, 93	pccld 12232	. . . . . . . . . . . . . . . . . . . 20 $/\$ $/\$
95	94	nn0zd 9311	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$
96		elfz5 9952	. . . . . . . . . . . . . . . . . . 19 $/\$
97	92, 95, 96	syl2anr 288	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$ $/\$
98		simpllr 524	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$ $/\$
99	84, 76	syl 14	. . . . . . . . . . . . . . . . . . . 20 $/\$ $/\$ $/\$
100	99	nnzd 9312	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$ $/\$
101	42	adantl 275	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$ $/\$
102		pcdvdsb 12251	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$
103	98, 100, 101, 102	syl3anc 1228	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$ $/\$
104	97, 103	bitr2d 188	. . . . . . . . . . . . . . . . 17 $/\$ $/\$ $/\$
105	104	ifbid 3541	. . . . . . . . . . . . . . . 16 $/\$ $/\$ $/\$
106	91, 105	eqtrd 2198	. . . . . . . . . . . . . . 15 $/\$ $/\$ $/\$
107	106	sumeq2dv 11309	. . . . . . . . . . . . . 14 $/\$ $/\$
108		1zzd 9218	. . . . . . . . . . . . . . . 16 $/\$ $/\$
109		eluzelz 9475	. . . . . . . . . . . . . . . . 17
110	109	adantl 275	. . . . . . . . . . . . . . . 16 $/\$ $/\$
111	108, 110	fzfigd 10366	. . . . . . . . . . . . . . 15 $/\$ $/\$
112		znq 9562	. . . . . . . . . . . . . . . . . 18 $/\$
113	100, 89, 112	syl2anc 409	. . . . . . . . . . . . . . . . 17 $/\$ $/\$ $/\$
114	113	flqcld 10212	. . . . . . . . . . . . . . . 16 $/\$ $/\$ $/\$
115	114	zcnd 9314	. . . . . . . . . . . . . . 15 $/\$ $/\$ $/\$
116		znq 9562	. . . . . . . . . . . . . . . . . 18 $/\$
117	85, 89, 116	syl2anc 409	. . . . . . . . . . . . . . . . 17 $/\$ $/\$ $/\$
118	117	flqcld 10212	. . . . . . . . . . . . . . . 16 $/\$ $/\$ $/\$
119	118	zcnd 9314	. . . . . . . . . . . . . . 15 $/\$ $/\$ $/\$
120	111, 115, 119	fsumsub 11393	. . . . . . . . . . . . . 14 $/\$ $/\$
121	94	nn0red 9168	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$
122	66	nn0red 9168	. . . . . . . . . . . . . . . . . . . 20 $/\$ $/\$
123		peano2re 8034	. . . . . . . . . . . . . . . . . . . 20
124	122, 123	syl 14	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$
125	110	zred 9313	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$
126	93	nnzd 9312	. . . . . . . . . . . . . . . . . . . . 21 $/\$ $/\$
127		zdcle 9267	. . . . . . . . . . . . . . . . . . . . 21 $/\$ DECID
128	95, 126, 127	syl2anc 409	. . . . . . . . . . . . . . . . . . . 20 $/\$ $/\$ DECID
129		zletric 9235	. . . . . . . . . . . . . . . . . . . . . . 23 $/\$ $\/$
130	95, 126, 129	syl2anc 409	. . . . . . . . . . . . . . . . . . . . . 22 $/\$ $/\$ $\/$
131	130	ord 714	. . . . . . . . . . . . . . . . . . . . 21 $/\$ $/\$
132	93	nnnn0d 9167	. . . . . . . . . . . . . . . . . . . . . . 23 $/\$ $/\$
133		pcdvdsb 12251	. . . . . . . . . . . . . . . . . . . . . . 23 $/\$ $/\$
134	70, 126, 132, 133	syl3anc 1228	. . . . . . . . . . . . . . . . . . . . . 22 $/\$ $/\$
135	87, 132	nnexpcld 10610	. . . . . . . . . . . . . . . . . . . . . . . . 25 $/\$ $/\$
136	135	nnzd 9312	. . . . . . . . . . . . . . . . . . . . . . . 24 $/\$ $/\$
137		dvdsle 11782	. . . . . . . . . . . . . . . . . . . . . . . 24 $/\$
138	136, 93, 137	syl2anc 409	. . . . . . . . . . . . . . . . . . . . . . 23 $/\$ $/\$
139	135	nnred 8870	. . . . . . . . . . . . . . . . . . . . . . . 24 $/\$ $/\$
140	139, 124	lenltd 8016	. . . . . . . . . . . . . . . . . . . . . . 23 $/\$ $/\$
141	138, 140	sylibd 148	. . . . . . . . . . . . . . . . . . . . . 22 $/\$ $/\$
142	134, 141	sylbid 149	. . . . . . . . . . . . . . . . . . . . 21 $/\$ $/\$
143	131, 142	syld 45	. . . . . . . . . . . . . . . . . . . 20 $/\$ $/\$
144		prmuz2 12063	. . . . . . . . . . . . . . . . . . . . . 22
145	144	ad2antlr 481	. . . . . . . . . . . . . . . . . . . . 21 $/\$ $/\$
146		bernneq3 10577	. . . . . . . . . . . . . . . . . . . . 21 $/\$
147	145, 132, 146	syl2anc 409	. . . . . . . . . . . . . . . . . . . 20 $/\$ $/\$
148		condc 843	. . . . . . . . . . . . . . . . . . . 20 DECID
149	128, 143, 147, 148	syl3c 63	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$
150		eluzle 9478	. . . . . . . . . . . . . . . . . . . 20
151	150	adantl 275	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$
152	121, 124, 125, 149, 151	letrd 8022	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$
153		eluz 9479	. . . . . . . . . . . . . . . . . . 19 $/\$
154	95, 110, 153	syl2anc 409	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$
155	152, 154	mpbird 166	. . . . . . . . . . . . . . . . 17 $/\$ $/\$
156		fzss2 9999	. . . . . . . . . . . . . . . . 17
157	155, 156	syl 14	. . . . . . . . . . . . . . . 16 $/\$ $/\$
158		elfzelz 9960	. . . . . . . . . . . . . . . . . . 19
159	158	adantl 275	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$ $/\$
160		1zzd 9218	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$ $/\$
161	95	adantr 274	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$ $/\$
162		fzdcel 9975	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$ DECID
163	159, 160, 161, 162	syl3anc 1228	. . . . . . . . . . . . . . . . 17 $/\$ $/\$ $/\$ DECID
164	163	ralrimiva 2539	. . . . . . . . . . . . . . . 16 $/\$ $/\$ DECID
165		sumhashdc 12277	. . . . . . . . . . . . . . . 16 $/\$ $/\$ DECID ♯
166	111, 157, 164, 165	syl3anc 1228	. . . . . . . . . . . . . . 15 $/\$ $/\$ ♯
167		hashfz1 10696	. . . . . . . . . . . . . . . 16 ♯
168	94, 167	syl 14	. . . . . . . . . . . . . . 15 $/\$ $/\$ ♯
169	166, 168	eqtrd 2198	. . . . . . . . . . . . . 14 $/\$ $/\$
170	107, 120, 169	3eqtr3d 2206	. . . . . . . . . . . . 13 $/\$ $/\$
171	111, 115	fsumcl 11341	. . . . . . . . . . . . . 14 $/\$ $/\$
172	111, 119	fsumcl 11341	. . . . . . . . . . . . . 14 $/\$ $/\$
173	94	nn0cnd 9169	. . . . . . . . . . . . . 14 $/\$ $/\$
174	171, 172, 173	subaddd 8227	. . . . . . . . . . . . 13 $/\$ $/\$
175	170, 174	mpbid 146	. . . . . . . . . . . 12 $/\$ $/\$
176	83, 175	eqeq12d 2180	. . . . . . . . . . 11 $/\$ $/\$
177	65, 176	syl5ib 153	. . . . . . . . . 10 $/\$ $/\$
178	177	ralimdva 2533	. . . . . . . . 9 $/\$
179	64, 178	syld 45	. . . . . . . 8 $/\$
180	179	ex 114	. . . . . . 7
181	180	a2d 26	. . . . . 6
182	8, 16, 24, 32, 56, 181	nn0ind 9305	. . . . 5
183	182	imp 123	. . . 4 $/\$
184		oveq2 5850	. . . . . . 7
185	184	sumeq1d 11307	. . . . . 6
186	185	eqeq2d 2177	. . . . 5
187	186	rspcv 2826	. . . 4
188	183, 187	syl5 32	. . 3 $/\$
189	188	3impib 1191	. 2 $/\$ $/\$
190	189	3com12 1197	1 $/\$ $/\$

Colors of variables: wff set class

Syntax hints:

wn 3

wi 4 $/\$ wa 103

wb 104 $\/$ wo 698 DECID wdc 824 $/\$ w3a 968

wceq 1343

wcel 2136

wne 2336

wral 2444

wss 3116

cif 3520 class class class wbr 3982

cfv 5188 (class class class)co 5842

cfn 6706

cr 7752

cc0 7753

c1 7754

caddc 7756

cmul 7758

clt 7933

cle 7934

cmin 8069

cdiv 8568

cn 8857

c2 8908

cn0 9114

cz 9191

cuz 9466

cq 9557

cfz 9944

cfl 10203

cexp 10454

cfa 10638 ♯chash 10688

csu 11294

cdvds 11727

cprime 12039

cpc 12216

This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-ia1 105 ax-ia2 106 ax-ia3 107 ax-in1 604 ax-in2 605 ax-io 699 ax-5 1435 ax-7 1436 ax-gen 1437 ax-ie1 1481 ax-ie2 1482 ax-8 1492 ax-10 1493 ax-11 1494 ax-i12 1495 ax-bndl 1497 ax-4 1498 ax-17 1514 ax-i9 1518 ax-ial 1522 ax-i5r 1523 ax-13 2138 ax-14 2139 ax-ext 2147 ax-coll 4097 ax-sep 4100 ax-nul 4108 ax-pow 4153 ax-pr 4187 ax-un 4411 ax-setind 4514 ax-iinf 4565 ax-cnex 7844 ax-resscn 7845 ax-1cn 7846 ax-1re 7847 ax-icn 7848 ax-addcl 7849 ax-addrcl 7850 ax-mulcl 7851 ax-mulrcl 7852 ax-addcom 7853 ax-mulcom 7854 ax-addass 7855 ax-mulass 7856 ax-distr 7857 ax-i2m1 7858 ax-0lt1 7859 ax-1rid 7860 ax-0id 7861 ax-rnegex 7862 ax-precex 7863 ax-cnre 7864 ax-pre-ltirr 7865 ax-pre-ltwlin 7866 ax-pre-lttrn 7867 ax-pre-apti 7868 ax-pre-ltadd 7869 ax-pre-mulgt0 7870 ax-pre-mulext 7871 ax-arch 7872 ax-caucvg 7873

This theorem depends on definitions: df-bi 116 df-stab 821 df-dc 825 df-3or 969 df-3an 970 df-tru 1346 df-fal 1349 df-nf 1449 df-sb 1751 df-eu 2017 df-mo 2018 df-clab 2152 df-cleq 2158 df-clel 2161 df-nfc 2297 df-ne 2337 df-nel 2432 df-ral 2449 df-rex 2450 df-reu 2451 df-rmo 2452 df-rab 2453 df-v 2728 df-sbc 2952 df-csb 3046 df-dif 3118 df-un 3120 df-in 3122 df-ss 3129 df-nul 3410 df-if 3521 df-pw 3561 df-sn 3582 df-pr 3583 df-op 3585 df-uni 3790 df-int 3825 df-iun 3868 df-br 3983 df-opab 4044 df-mpt 4045 df-tr 4081 df-id 4271 df-po 4274 df-iso 4275 df-iord 4344 df-on 4346 df-ilim 4347 df-suc 4349 df-iom 4568 df-xp 4610 df-rel 4611 df-cnv 4612 df-co 4613 df-dm 4614 df-rn 4615 df-res 4616 df-ima 4617 df-iota 5153 df-fun 5190 df-fn 5191 df-f 5192 df-f1 5193 df-fo 5194 df-f1o 5195 df-fv 5196 df-isom 5197 df-riota 5798 df-ov 5845 df-oprab 5846 df-mpo 5847 df-1st 6108 df-2nd 6109 df-recs 6273 df-irdg 6338 df-frec 6359 df-1o 6384 df-2o 6385 df-oadd 6388 df-er 6501 df-en 6707 df-dom 6708 df-fin 6709 df-sup 6949 df-inf 6950 df-pnf 7935 df-mnf 7936 df-xr 7937 df-ltxr 7938 df-le 7939 df-sub 8071 df-neg 8072 df-reap 8473 df-ap 8480 df-div 8569 df-inn 8858 df-2 8916 df-3 8917 df-4 8918 df-n0 9115 df-z 9192 df-uz 9467 df-q 9558 df-rp 9590 df-fz 9945 df-fzo 10078 df-fl 10205 df-mod 10258 df-seqfrec 10381 df-exp 10455 df-fac 10639 df-ihash 10689 df-cj 10784 df-re 10785 df-im 10786 df-rsqrt 10940 df-abs 10941 df-clim 11220 df-sumdc 11295 df-dvds 11728 df-gcd 11876 df-prm 12040 df-pc 12217

This theorem is referenced by: pcbc 12281

W3C validator