pcfac - Intuitionistic Logic Explorer

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

Theorem pcfac 12302

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 5496	. . . . . . . 8
2		fveq2 5496	. . . . . . . . . 10
3	2	oveq2d 5869	. . . . . . . . 9
4		fvoveq1 5876	. . . . . . . . . 10
5	4	sumeq2sdv 11333	. . . . . . . . 9
6	3, 5	eqeq12d 2185	. . . . . . . 8
7	1, 6	raleqbidv 2677	. . . . . . 7
8	7	imbi2d 229	. . . . . 6
9		fveq2 5496	. . . . . . . 8
10		fveq2 5496	. . . . . . . . . 10
11	10	oveq2d 5869	. . . . . . . . 9
12		fvoveq1 5876	. . . . . . . . . 10
13	12	sumeq2sdv 11333	. . . . . . . . 9
14	11, 13	eqeq12d 2185	. . . . . . . 8
15	9, 14	raleqbidv 2677	. . . . . . 7
16	15	imbi2d 229	. . . . . 6
17		fveq2 5496	. . . . . . . 8
18		fveq2 5496	. . . . . . . . . 10
19	18	oveq2d 5869	. . . . . . . . 9
20		fvoveq1 5876	. . . . . . . . . 10
21	20	sumeq2sdv 11333	. . . . . . . . 9
22	19, 21	eqeq12d 2185	. . . . . . . 8
23	17, 22	raleqbidv 2677	. . . . . . 7
24	23	imbi2d 229	. . . . . 6
25		fveq2 5496	. . . . . . . 8
26		fveq2 5496	. . . . . . . . . 10
27	26	oveq2d 5869	. . . . . . . . 9
28		fvoveq1 5876	. . . . . . . . . 10
29	28	sumeq2sdv 11333	. . . . . . . . 9
30	27, 29	eqeq12d 2185	. . . . . . . 8
31	25, 30	raleqbidv 2677	. . . . . . 7
32	31	imbi2d 229	. . . . . 6
33		1zzd 9239	. . . . . . . . . 10 $/\$
34		eluzelz 9496	. . . . . . . . . . 11
35	34	adantl 275	. . . . . . . . . 10 $/\$
36	33, 35	fzfigd 10387	. . . . . . . . 9 $/\$
37		isumz 11352	. . . . . . . . . 10 $/\$ $/\$ DECID $\/$
38	37	olcs 731	. . . . . . . . 9
39	36, 38	syl 14	. . . . . . . 8 $/\$
40		0nn0 9150	. . . . . . . . . 10
41		elfznn 10010	. . . . . . . . . . . . 13
42	41	nnnn0d 9188	. . . . . . . . . . . 12
43		nn0uz 9521	. . . . . . . . . . . 12
44	42, 43	eleqtrdi 2263	. . . . . . . . . . 11
45	44	adantl 275	. . . . . . . . . 10 $/\$ $/\$
46		simpll 524	. . . . . . . . . 10 $/\$ $/\$
47		pcfaclem 12301	. . . . . . . . . 10 $/\$ $/\$
48	40, 45, 46, 47	mp3an2i 1337	. . . . . . . . 9 $/\$ $/\$
49	48	sumeq2dv 11331	. . . . . . . 8 $/\$
50		fac0 10662	. . . . . . . . . . 11
51	50	oveq2i 5864	. . . . . . . . . 10
52		pc1 12259	. . . . . . . . . 10
53	51, 52	eqtrid 2215	. . . . . . . . 9
54	53	adantr 274	. . . . . . . 8 $/\$
55	39, 49, 54	3eqtr4rd 2214	. . . . . . 7 $/\$
56	55	ralrimiva 2543	. . . . . 6
57		nn0z 9232	. . . . . . . . . . . 12
58	57	adantr 274	. . . . . . . . . . 11 $/\$
59		uzid 9501	. . . . . . . . . . 11
60		peano2uz 9542	. . . . . . . . . . 11
61	58, 59, 60	3syl 17	. . . . . . . . . 10 $/\$
62		uzss 9507	. . . . . . . . . 10
63		ssralv 3211	. . . . . . . . . 10
64	61, 62, 63	3syl 17	. . . . . . . . 9 $/\$
65		oveq1 5860	. . . . . . . . . . 11
66		simpll 524	. . . . . . . . . . . . . . 15 $/\$ $/\$
67		facp1 10664	. . . . . . . . . . . . . . 15
68	66, 67	syl 14	. . . . . . . . . . . . . 14 $/\$ $/\$
69	68	oveq2d 5869	. . . . . . . . . . . . 13 $/\$ $/\$
70		simplr 525	. . . . . . . . . . . . . 14 $/\$ $/\$
71		faccl 10669	. . . . . . . . . . . . . . 15
72		nnz 9231	. . . . . . . . . . . . . . . 16
73		nnne0 8906	. . . . . . . . . . . . . . . 16
74	72, 73	jca 304	. . . . . . . . . . . . . . 15 $/\$
75	66, 71, 74	3syl 17	. . . . . . . . . . . . . 14 $/\$ $/\$ $/\$
76		nn0p1nn 9174	. . . . . . . . . . . . . . 15
77		nnz 9231	. . . . . . . . . . . . . . . 16
78		nnne0 8906	. . . . . . . . . . . . . . . 16
79	77, 78	jca 304	. . . . . . . . . . . . . . 15 $/\$
80	66, 76, 79	3syl 17	. . . . . . . . . . . . . 14 $/\$ $/\$ $/\$
81		pcmul 12255	. . . . . . . . . . . . . 14 $/\$ $/\$ $/\$ $/\$
82	70, 75, 80, 81	syl3anc 1233	. . . . . . . . . . . . 13 $/\$ $/\$
83	69, 82	eqtr2d 2204	. . . . . . . . . . . 12 $/\$ $/\$
84	66	adantr 274	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$ $/\$
85	84	nn0zd 9332	. . . . . . . . . . . . . . . . 17 $/\$ $/\$ $/\$
86		prmnn 12064	. . . . . . . . . . . . . . . . . . 19
87	86	ad2antlr 486	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$
88		nnexpcl 10489	. . . . . . . . . . . . . . . . . 18 $/\$
89	87, 42, 88	syl2an 287	. . . . . . . . . . . . . . . . 17 $/\$ $/\$ $/\$
90		fldivp1 12300	. . . . . . . . . . . . . . . . 17 $/\$
91	85, 89, 90	syl2anc 409	. . . . . . . . . . . . . . . 16 $/\$ $/\$ $/\$
92		elfzuz 9977	. . . . . . . . . . . . . . . . . . 19
93	66, 76	syl 14	. . . . . . . . . . . . . . . . . . . . 21 $/\$ $/\$
94	70, 93	pccld 12254	. . . . . . . . . . . . . . . . . . . 20 $/\$ $/\$
95	94	nn0zd 9332	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$
96		elfz5 9973	. . . . . . . . . . . . . . . . . . 19 $/\$
97	92, 95, 96	syl2anr 288	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$ $/\$
98		simpllr 529	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$ $/\$
99	84, 76	syl 14	. . . . . . . . . . . . . . . . . . . 20 $/\$ $/\$ $/\$
100	99	nnzd 9333	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$ $/\$
101	42	adantl 275	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$ $/\$
102		pcdvdsb 12273	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$
103	98, 100, 101, 102	syl3anc 1233	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$ $/\$
104	97, 103	bitr2d 188	. . . . . . . . . . . . . . . . 17 $/\$ $/\$ $/\$
105	104	ifbid 3547	. . . . . . . . . . . . . . . 16 $/\$ $/\$ $/\$
106	91, 105	eqtrd 2203	. . . . . . . . . . . . . . 15 $/\$ $/\$ $/\$
107	106	sumeq2dv 11331	. . . . . . . . . . . . . 14 $/\$ $/\$
108		1zzd 9239	. . . . . . . . . . . . . . . 16 $/\$ $/\$
109		eluzelz 9496	. . . . . . . . . . . . . . . . 17
110	109	adantl 275	. . . . . . . . . . . . . . . 16 $/\$ $/\$
111	108, 110	fzfigd 10387	. . . . . . . . . . . . . . 15 $/\$ $/\$
112		znq 9583	. . . . . . . . . . . . . . . . . 18 $/\$
113	100, 89, 112	syl2anc 409	. . . . . . . . . . . . . . . . 17 $/\$ $/\$ $/\$
114	113	flqcld 10233	. . . . . . . . . . . . . . . 16 $/\$ $/\$ $/\$
115	114	zcnd 9335	. . . . . . . . . . . . . . 15 $/\$ $/\$ $/\$
116		znq 9583	. . . . . . . . . . . . . . . . . 18 $/\$
117	85, 89, 116	syl2anc 409	. . . . . . . . . . . . . . . . 17 $/\$ $/\$ $/\$
118	117	flqcld 10233	. . . . . . . . . . . . . . . 16 $/\$ $/\$ $/\$
119	118	zcnd 9335	. . . . . . . . . . . . . . 15 $/\$ $/\$ $/\$
120	111, 115, 119	fsumsub 11415	. . . . . . . . . . . . . 14 $/\$ $/\$
121	94	nn0red 9189	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$
122	66	nn0red 9189	. . . . . . . . . . . . . . . . . . . 20 $/\$ $/\$
123		peano2re 8055	. . . . . . . . . . . . . . . . . . . 20
124	122, 123	syl 14	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$
125	110	zred 9334	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$
126	93	nnzd 9333	. . . . . . . . . . . . . . . . . . . . 21 $/\$ $/\$
127		zdcle 9288	. . . . . . . . . . . . . . . . . . . . 21 $/\$ DECID
128	95, 126, 127	syl2anc 409	. . . . . . . . . . . . . . . . . . . 20 $/\$ $/\$ DECID
129		zletric 9256	. . . . . . . . . . . . . . . . . . . . . . 23 $/\$ $\/$
130	95, 126, 129	syl2anc 409	. . . . . . . . . . . . . . . . . . . . . 22 $/\$ $/\$ $\/$
131	130	ord 719	. . . . . . . . . . . . . . . . . . . . 21 $/\$ $/\$
132	93	nnnn0d 9188	. . . . . . . . . . . . . . . . . . . . . . 23 $/\$ $/\$
133		pcdvdsb 12273	. . . . . . . . . . . . . . . . . . . . . . 23 $/\$ $/\$
134	70, 126, 132, 133	syl3anc 1233	. . . . . . . . . . . . . . . . . . . . . 22 $/\$ $/\$
135	87, 132	nnexpcld 10631	. . . . . . . . . . . . . . . . . . . . . . . . 25 $/\$ $/\$
136	135	nnzd 9333	. . . . . . . . . . . . . . . . . . . . . . . 24 $/\$ $/\$
137		dvdsle 11804	. . . . . . . . . . . . . . . . . . . . . . . 24 $/\$
138	136, 93, 137	syl2anc 409	. . . . . . . . . . . . . . . . . . . . . . 23 $/\$ $/\$
139	135	nnred 8891	. . . . . . . . . . . . . . . . . . . . . . . 24 $/\$ $/\$
140	139, 124	lenltd 8037	. . . . . . . . . . . . . . . . . . . . . . 23 $/\$ $/\$
141	138, 140	sylibd 148	. . . . . . . . . . . . . . . . . . . . . 22 $/\$ $/\$
142	134, 141	sylbid 149	. . . . . . . . . . . . . . . . . . . . 21 $/\$ $/\$
143	131, 142	syld 45	. . . . . . . . . . . . . . . . . . . 20 $/\$ $/\$
144		prmuz2 12085	. . . . . . . . . . . . . . . . . . . . . 22
145	144	ad2antlr 486	. . . . . . . . . . . . . . . . . . . . 21 $/\$ $/\$
146		bernneq3 10598	. . . . . . . . . . . . . . . . . . . . 21 $/\$
147	145, 132, 146	syl2anc 409	. . . . . . . . . . . . . . . . . . . 20 $/\$ $/\$
148		condc 848	. . . . . . . . . . . . . . . . . . . 20 DECID
149	128, 143, 147, 148	syl3c 63	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$
150		eluzle 9499	. . . . . . . . . . . . . . . . . . . 20
151	150	adantl 275	. . . . . . . . . . . . . . . . . . 19 $/\$ $/\$
152	121, 124, 125, 149, 151	letrd 8043	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$
153		eluz 9500	. . . . . . . . . . . . . . . . . . 19 $/\$
154	95, 110, 153	syl2anc 409	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$
155	152, 154	mpbird 166	. . . . . . . . . . . . . . . . 17 $/\$ $/\$
156		fzss2 10020	. . . . . . . . . . . . . . . . 17
157	155, 156	syl 14	. . . . . . . . . . . . . . . 16 $/\$ $/\$
158		elfzelz 9981	. . . . . . . . . . . . . . . . . . 19
159	158	adantl 275	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$ $/\$
160		1zzd 9239	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$ $/\$
161	95	adantr 274	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$ $/\$
162		fzdcel 9996	. . . . . . . . . . . . . . . . . 18 $/\$ $/\$ DECID
163	159, 160, 161, 162	syl3anc 1233	. . . . . . . . . . . . . . . . 17 $/\$ $/\$ $/\$ DECID
164	163	ralrimiva 2543	. . . . . . . . . . . . . . . 16 $/\$ $/\$ DECID
165		sumhashdc 12299	. . . . . . . . . . . . . . . 16 $/\$ $/\$ DECID ♯
166	111, 157, 164, 165	syl3anc 1233	. . . . . . . . . . . . . . 15 $/\$ $/\$ ♯
167		hashfz1 10717	. . . . . . . . . . . . . . . 16 ♯
168	94, 167	syl 14	. . . . . . . . . . . . . . 15 $/\$ $/\$ ♯
169	166, 168	eqtrd 2203	. . . . . . . . . . . . . 14 $/\$ $/\$
170	107, 120, 169	3eqtr3d 2211	. . . . . . . . . . . . 13 $/\$ $/\$
171	111, 115	fsumcl 11363	. . . . . . . . . . . . . 14 $/\$ $/\$
172	111, 119	fsumcl 11363	. . . . . . . . . . . . . 14 $/\$ $/\$
173	94	nn0cnd 9190	. . . . . . . . . . . . . 14 $/\$ $/\$
174	171, 172, 173	subaddd 8248	. . . . . . . . . . . . 13 $/\$ $/\$
175	170, 174	mpbid 146	. . . . . . . . . . . 12 $/\$ $/\$
176	83, 175	eqeq12d 2185	. . . . . . . . . . 11 $/\$ $/\$
177	65, 176	syl5ib 153	. . . . . . . . . 10 $/\$ $/\$
178	177	ralimdva 2537	. . . . . . . . 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 9326	. . . . 5
183	182	imp 123	. . . 4 $/\$
184		oveq2 5861	. . . . . . 7
185	184	sumeq1d 11329	. . . . . 6
186	185	eqeq2d 2182	. . . . 5
187	186	rspcv 2830	. . . 4
188	183, 187	syl5 32	. . 3 $/\$
189	188	3impib 1196	. 2 $/\$ $/\$
190	189	3com12 1202	1 $/\$ $/\$

Colors of variables: wff set class

Syntax hints:

wn 3

wi 4 $/\$ wa 103

wb 104 $\/$ wo 703 DECID wdc 829 $/\$ w3a 973

wceq 1348

wcel 2141

wne 2340

wral 2448

wss 3121

cif 3526 class class class wbr 3989

cfv 5198 (class class class)co 5853

cfn 6718

cr 7773

cc0 7774

c1 7775

caddc 7777

cmul 7779

clt 7954

cle 7955

cmin 8090

cdiv 8589

cn 8878

c2 8929

cn0 9135

cz 9212

cuz 9487

cq 9578

cfz 9965

cfl 10224

cexp 10475

cfa 10659 ♯chash 10709

csu 11316

cdvds 11749

cprime 12061

cpc 12238

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 609 ax-in2 610 ax-io 704 ax-5 1440 ax-7 1441 ax-gen 1442 ax-ie1 1486 ax-ie2 1487 ax-8 1497 ax-10 1498 ax-11 1499 ax-i12 1500 ax-bndl 1502 ax-4 1503 ax-17 1519 ax-i9 1523 ax-ial 1527 ax-i5r 1528 ax-13 2143 ax-14 2144 ax-ext 2152 ax-coll 4104 ax-sep 4107 ax-nul 4115 ax-pow 4160 ax-pr 4194 ax-un 4418 ax-setind 4521 ax-iinf 4572 ax-cnex 7865 ax-resscn 7866 ax-1cn 7867 ax-1re 7868 ax-icn 7869 ax-addcl 7870 ax-addrcl 7871 ax-mulcl 7872 ax-mulrcl 7873 ax-addcom 7874 ax-mulcom 7875 ax-addass 7876 ax-mulass 7877 ax-distr 7878 ax-i2m1 7879 ax-0lt1 7880 ax-1rid 7881 ax-0id 7882 ax-rnegex 7883 ax-precex 7884 ax-cnre 7885 ax-pre-ltirr 7886 ax-pre-ltwlin 7887 ax-pre-lttrn 7888 ax-pre-apti 7889 ax-pre-ltadd 7890 ax-pre-mulgt0 7891 ax-pre-mulext 7892 ax-arch 7893 ax-caucvg 7894

This theorem depends on definitions: df-bi 116 df-stab 826 df-dc 830 df-3or 974 df-3an 975 df-tru 1351 df-fal 1354 df-nf 1454 df-sb 1756 df-eu 2022 df-mo 2023 df-clab 2157 df-cleq 2163 df-clel 2166 df-nfc 2301 df-ne 2341 df-nel 2436 df-ral 2453 df-rex 2454 df-reu 2455 df-rmo 2456 df-rab 2457 df-v 2732 df-sbc 2956 df-csb 3050 df-dif 3123 df-un 3125 df-in 3127 df-ss 3134 df-nul 3415 df-if 3527 df-pw 3568 df-sn 3589 df-pr 3590 df-op 3592 df-uni 3797 df-int 3832 df-iun 3875 df-br 3990 df-opab 4051 df-mpt 4052 df-tr 4088 df-id 4278 df-po 4281 df-iso 4282 df-iord 4351 df-on 4353 df-ilim 4354 df-suc 4356 df-iom 4575 df-xp 4617 df-rel 4618 df-cnv 4619 df-co 4620 df-dm 4621 df-rn 4622 df-res 4623 df-ima 4624 df-iota 5160 df-fun 5200 df-fn 5201 df-f 5202 df-f1 5203 df-fo 5204 df-f1o 5205 df-fv 5206 df-isom 5207 df-riota 5809 df-ov 5856 df-oprab 5857 df-mpo 5858 df-1st 6119 df-2nd 6120 df-recs 6284 df-irdg 6349 df-frec 6370 df-1o 6395 df-2o 6396 df-oadd 6399 df-er 6513 df-en 6719 df-dom 6720 df-fin 6721 df-sup 6961 df-inf 6962 df-pnf 7956 df-mnf 7957 df-xr 7958 df-ltxr 7959 df-le 7960 df-sub 8092 df-neg 8093 df-reap 8494 df-ap 8501 df-div 8590 df-inn 8879 df-2 8937 df-3 8938 df-4 8939 df-n0 9136 df-z 9213 df-uz 9488 df-q 9579 df-rp 9611 df-fz 9966 df-fzo 10099 df-fl 10226 df-mod 10279 df-seqfrec 10402 df-exp 10476 df-fac 10660 df-ihash 10710 df-cj 10806 df-re 10807 df-im 10808 df-rsqrt 10962 df-abs 10963 df-clim 11242 df-sumdc 11317 df-dvds 11750 df-gcd 11898 df-prm 12062 df-pc 12239

This theorem is referenced by: pcbc 12303

W3C validator