Metamath Proof Explorer


Theorem oddpwdc

Description: Lemma for eulerpart . The function F that decomposes a number into its "odd" and "even" parts, which is to say the largest power of two and largest odd divisor of a number, is a bijection from pairs of a nonnegative integer and an odd number to positive integers. (Contributed by Thierry Arnoux, 15-Aug-2017)

Ref Expression
Hypotheses oddpwdc.j J=z|¬2z
oddpwdc.f F=xJ,y02yx
Assertion oddpwdc F:J×01-1 onto

Proof

Step Hyp Ref Expression
1 oddpwdc.j J=z|¬2z
2 oddpwdc.f F=xJ,y02yx
3 2nn 2
4 3 a1i y0xJ2
5 simpl y0xJy0
6 4 5 nnexpcld y0xJ2y
7 ssrab2 z|¬2z
8 1 7 eqsstri J
9 simpr y0xJxJ
10 8 9 sselid y0xJx
11 6 10 nnmulcld y0xJ2yx
12 11 ancoms xJy02yx
13 12 adantl xJy02yx
14 id aa
15 3 a1i a2
16 nn0ssre 0
17 ltso <Or
18 soss 0<Or<Or0
19 16 17 18 mp2 <Or0
20 19 a1i a<Or0
21 0zd a0
22 ssrab2 k0|2ka0
23 22 a1i ak0|2ka0
24 nnz aa
25 oveq2 k=n2k=2n
26 25 breq1d k=n2ka2na
27 26 elrab nk0|2kan02na
28 simprl an02nan0
29 28 nn0red an02nan
30 3 a1i an02na2
31 30 28 nnexpcld an02na2n
32 31 nnred an02na2n
33 simpl an02naa
34 33 nnred an02naa
35 2re 2
36 35 leidi 22
37 nexple n0222n2n
38 35 36 37 mp3an23 n0n2n
39 38 ad2antrl an02nan2n
40 31 nnzd an02na2n
41 simprr an02na2na
42 dvdsle 2na2na2na
43 42 imp 2na2na2na
44 40 33 41 43 syl21anc an02na2na
45 29 32 34 39 44 letrd an02nana
46 27 45 sylan2b ank0|2kana
47 46 ralrimiva ank0|2kana
48 brralrspcev ank0|2kanamnk0|2kanm
49 24 47 48 syl2anc amnk0|2kanm
50 nn0uz 0=0
51 50 uzsupss 0k0|2ka0mnk0|2kanmm0nk0|2ka¬m<nn0n<mok0|2kan<o
52 21 23 49 51 syl3anc am0nk0|2ka¬m<nn0n<mok0|2kan<o
53 20 52 supcl asupk0|2ka0<0
54 15 53 nnexpcld a2supk0|2ka0<
55 fzfi 0aFin
56 0zd ank0|2ka0
57 24 adantr ank0|2kaa
58 27 28 sylan2b ank0|2kan0
59 58 nn0zd ank0|2kan
60 58 nn0ge0d ank0|2ka0n
61 56 57 59 60 46 elfzd ank0|2kan0a
62 61 ex ank0|2kan0a
63 62 ssrdv ak0|2ka0a
64 ssfi 0aFink0|2ka0ak0|2kaFin
65 55 63 64 sylancr ak0|2kaFin
66 0nn0 00
67 66 a1i a00
68 2cn 2
69 exp0 220=1
70 68 69 ax-mp 20=1
71 1dvds a1a
72 24 71 syl a1a
73 70 72 eqbrtrid a20a
74 oveq2 k=02k=20
75 74 breq1d k=02ka20a
76 75 elrab 0k0|2ka0020a
77 67 73 76 sylanbrc a0k0|2ka
78 77 ne0d ak0|2ka
79 fisupcl <Or0k0|2kaFink0|2kak0|2ka0supk0|2ka0<k0|2ka
80 20 65 78 23 79 syl13anc asupk0|2ka0<k0|2ka
81 oveq2 k=l2k=2l
82 81 breq1d k=l2ka2la
83 82 cbvrabv k0|2ka=l0|2la
84 80 83 eleqtrdi asupk0|2ka0<l0|2la
85 oveq2 l=supk0|2ka0<2l=2supk0|2ka0<
86 85 breq1d l=supk0|2ka0<2la2supk0|2ka0<a
87 86 elrab supk0|2ka0<l0|2lasupk0|2ka0<02supk0|2ka0<a
88 84 87 sylib asupk0|2ka0<02supk0|2ka0<a
89 88 simprd a2supk0|2ka0<a
90 nndivdvds a2supk0|2ka0<2supk0|2ka0<aa2supk0|2ka0<
91 90 biimpa a2supk0|2ka0<2supk0|2ka0<aa2supk0|2ka0<
92 14 54 89 91 syl21anc aa2supk0|2ka0<
93 1nn0 10
94 93 a1i a10
95 53 94 nn0addcld asupk0|2ka0<+10
96 53 nn0red asupk0|2ka0<
97 96 ltp1d asupk0|2ka0<<supk0|2ka0<+1
98 20 52 supub asupk0|2ka0<+1k0|2ka¬supk0|2ka0<<supk0|2ka0<+1
99 97 98 mt2d a¬supk0|2ka0<+1k0|2ka
100 83 eleq2i supk0|2ka0<+1k0|2kasupk0|2ka0<+1l0|2la
101 99 100 sylnib a¬supk0|2ka0<+1l0|2la
102 oveq2 l=supk0|2ka0<+12l=2supk0|2ka0<+1
103 102 breq1d l=supk0|2ka0<+12la2supk0|2ka0<+1a
104 103 elrab supk0|2ka0<+1l0|2lasupk0|2ka0<+102supk0|2ka0<+1a
105 101 104 sylnib a¬supk0|2ka0<+102supk0|2ka0<+1a
106 imnan supk0|2ka0<+10¬2supk0|2ka0<+1a¬supk0|2ka0<+102supk0|2ka0<+1a
107 105 106 sylibr asupk0|2ka0<+10¬2supk0|2ka0<+1a
108 95 107 mpd a¬2supk0|2ka0<+1a
109 expp1 2supk0|2ka0<02supk0|2ka0<+1=2supk0|2ka0<2
110 68 53 109 sylancr a2supk0|2ka0<+1=2supk0|2ka0<2
111 110 breq1d a2supk0|2ka0<+1a2supk0|2ka0<2a
112 108 111 mtbid a¬2supk0|2ka0<2a
113 nncn aa
114 54 nncnd a2supk0|2ka0<
115 54 nnne0d a2supk0|2ka0<0
116 113 114 115 divcan2d a2supk0|2ka0<a2supk0|2ka0<=a
117 116 eqcomd aa=2supk0|2ka0<a2supk0|2ka0<
118 117 breq2d a2supk0|2ka0<2a2supk0|2ka0<22supk0|2ka0<a2supk0|2ka0<
119 15 nnzd a2
120 92 nnzd aa2supk0|2ka0<
121 54 nnzd a2supk0|2ka0<
122 dvdscmulr 2a2supk0|2ka0<2supk0|2ka0<2supk0|2ka0<02supk0|2ka0<22supk0|2ka0<a2supk0|2ka0<2a2supk0|2ka0<
123 119 120 121 115 122 syl112anc a2supk0|2ka0<22supk0|2ka0<a2supk0|2ka0<2a2supk0|2ka0<
124 118 123 bitrd a2supk0|2ka0<2a2a2supk0|2ka0<
125 112 124 mtbid a¬2a2supk0|2ka0<
126 breq2 z=a2supk0|2ka0<2z2a2supk0|2ka0<
127 126 notbid z=a2supk0|2ka0<¬2z¬2a2supk0|2ka0<
128 127 1 elrab2 a2supk0|2ka0<Ja2supk0|2ka0<¬2a2supk0|2ka0<
129 92 125 128 sylanbrc aa2supk0|2ka0<J
130 129 53 jca aa2supk0|2ka0<Jsupk0|2ka0<0
131 130 adantl aa2supk0|2ka0<Jsupk0|2ka0<0
132 simpr xJy0a=2yxa=2yx
133 3 a1i xJy0a=2yx2
134 simplr xJy0a=2yxy0
135 133 134 nnexpcld xJy0a=2yx2y
136 8 sseli xJx
137 136 ad2antrr xJy0a=2yxx
138 135 137 nnmulcld xJy0a=2yx2yx
139 132 138 eqeltrd xJy0a=2yxa
140 simplll xJy0a=2yxy<supk0|2ka0<xJ
141 breq2 z=x2z2x
142 141 notbid z=x¬2z¬2x
143 142 1 elrab2 xJx¬2x
144 143 simprbi xJ¬2x
145 2z 2
146 134 adantr xJy0a=2yxy<supk0|2ka0<y0
147 146 nn0zd xJy0a=2yxy<supk0|2ka0<y
148 19 a1i xJy0a=2yxy<supk0|2ka0<<Or0
149 139 52 syl xJy0a=2yxm0nk0|2ka¬m<nn0n<mok0|2kan<o
150 149 adantr xJy0a=2yxy<supk0|2ka0<m0nk0|2ka¬m<nn0n<mok0|2kan<o
151 148 150 supcl xJy0a=2yxy<supk0|2ka0<supk0|2ka0<0
152 151 nn0zd xJy0a=2yxy<supk0|2ka0<supk0|2ka0<
153 simpr xJy0a=2yxy<supk0|2ka0<y<supk0|2ka0<
154 znnsub ysupk0|2ka0<y<supk0|2ka0<supk0|2ka0<y
155 154 biimpa ysupk0|2ka0<y<supk0|2ka0<supk0|2ka0<y
156 147 152 153 155 syl21anc xJy0a=2yxy<supk0|2ka0<supk0|2ka0<y
157 iddvdsexp 2supk0|2ka0<y22supk0|2ka0<y
158 145 156 157 sylancr xJy0a=2yxy<supk0|2ka0<22supk0|2ka0<y
159 145 a1i xJy0a=2yxy<supk0|2ka0<2
160 139 120 syl xJy0a=2yxa2supk0|2ka0<
161 160 adantr xJy0a=2yxy<supk0|2ka0<a2supk0|2ka0<
162 156 nnnn0d xJy0a=2yxy<supk0|2ka0<supk0|2ka0<y0
163 zexpcl 2supk0|2ka0<y02supk0|2ka0<y
164 145 162 163 sylancr xJy0a=2yxy<supk0|2ka0<2supk0|2ka0<y
165 dvdsmultr2 2a2supk0|2ka0<2supk0|2ka0<y22supk0|2ka0<y2a2supk0|2ka0<2supk0|2ka0<y
166 159 161 164 165 syl3anc xJy0a=2yxy<supk0|2ka0<22supk0|2ka0<y2a2supk0|2ka0<2supk0|2ka0<y
167 158 166 mpd xJy0a=2yxy<supk0|2ka0<2a2supk0|2ka0<2supk0|2ka0<y
168 137 adantr xJy0a=2yxy<supk0|2ka0<x
169 168 nncnd xJy0a=2yxy<supk0|2ka0<x
170 2cnd xJy0a=2yxy<supk0|2ka0<2
171 170 162 expcld xJy0a=2yxy<supk0|2ka0<2supk0|2ka0<y
172 139 adantr xJy0a=2yxy<supk0|2ka0<a
173 172 nncnd xJy0a=2yxy<supk0|2ka0<a
174 172 114 syl xJy0a=2yxy<supk0|2ka0<2supk0|2ka0<
175 2ne0 20
176 175 a1i xJy0a=2yxy<supk0|2ka0<20
177 170 176 152 expne0d xJy0a=2yxy<supk0|2ka0<2supk0|2ka0<0
178 173 174 177 divcld xJy0a=2yxy<supk0|2ka0<a2supk0|2ka0<
179 171 178 mulcld xJy0a=2yxy<supk0|2ka0<2supk0|2ka0<ya2supk0|2ka0<
180 170 146 expcld xJy0a=2yxy<supk0|2ka0<2y
181 170 176 147 expne0d xJy0a=2yxy<supk0|2ka0<2y0
182 172 117 syl xJy0a=2yxy<supk0|2ka0<a=2supk0|2ka0<a2supk0|2ka0<
183 simplr xJy0a=2yxy<supk0|2ka0<a=2yx
184 146 nn0cnd xJy0a=2yxy<supk0|2ka0<y
185 151 nn0cnd xJy0a=2yxy<supk0|2ka0<supk0|2ka0<
186 184 185 pncan3d xJy0a=2yxy<supk0|2ka0<y+supk0|2ka0<-y=supk0|2ka0<
187 186 oveq2d xJy0a=2yxy<supk0|2ka0<2y+supk0|2ka0<-y=2supk0|2ka0<
188 170 162 146 expaddd xJy0a=2yxy<supk0|2ka0<2y+supk0|2ka0<-y=2y2supk0|2ka0<y
189 187 188 eqtr3d xJy0a=2yxy<supk0|2ka0<2supk0|2ka0<=2y2supk0|2ka0<y
190 189 oveq1d xJy0a=2yxy<supk0|2ka0<2supk0|2ka0<a2supk0|2ka0<=2y2supk0|2ka0<ya2supk0|2ka0<
191 182 183 190 3eqtr3d xJy0a=2yxy<supk0|2ka0<2yx=2y2supk0|2ka0<ya2supk0|2ka0<
192 180 171 178 mulassd xJy0a=2yxy<supk0|2ka0<2y2supk0|2ka0<ya2supk0|2ka0<=2y2supk0|2ka0<ya2supk0|2ka0<
193 191 192 eqtrd xJy0a=2yxy<supk0|2ka0<2yx=2y2supk0|2ka0<ya2supk0|2ka0<
194 169 179 180 181 193 mulcanad xJy0a=2yxy<supk0|2ka0<x=2supk0|2ka0<ya2supk0|2ka0<
195 178 171 mulcomd xJy0a=2yxy<supk0|2ka0<a2supk0|2ka0<2supk0|2ka0<y=2supk0|2ka0<ya2supk0|2ka0<
196 194 195 eqtr4d xJy0a=2yxy<supk0|2ka0<x=a2supk0|2ka0<2supk0|2ka0<y
197 167 196 breqtrrd xJy0a=2yxy<supk0|2ka0<2x
198 144 197 nsyl3 xJy0a=2yxy<supk0|2ka0<¬xJ
199 140 198 pm2.65da xJy0a=2yx¬y<supk0|2ka0<
200 137 nnzd xJy0a=2yxx
201 135 nnzd xJy0a=2yx2y
202 139 nnzd xJy0a=2yxa
203 135 nncnd xJy0a=2yx2y
204 137 nncnd xJy0a=2yxx
205 203 204 mulcomd xJy0a=2yx2yx=x2y
206 132 205 eqtr2d xJy0a=2yxx2y=a
207 dvds0lem x2yax2y=a2ya
208 200 201 202 206 207 syl31anc xJy0a=2yx2ya
209 oveq2 k=y2k=2y
210 209 breq1d k=y2ka2ya
211 210 elrab yk0|2kay02ya
212 134 208 211 sylanbrc xJy0a=2yxyk0|2ka
213 19 a1i xJy0a=2yx<Or0
214 213 149 supub xJy0a=2yxyk0|2ka¬supk0|2ka0<<y
215 212 214 mpd xJy0a=2yx¬supk0|2ka0<<y
216 134 nn0red xJy0a=2yxy
217 139 96 syl xJy0a=2yxsupk0|2ka0<
218 216 217 lttri3d xJy0a=2yxy=supk0|2ka0<¬y<supk0|2ka0<¬supk0|2ka0<<y
219 199 215 218 mpbir2and xJy0a=2yxy=supk0|2ka0<
220 simplr xJy0a=2yxy=supk0|2ka0<a=2yx
221 139 adantr xJy0a=2yxy=supk0|2ka0<a
222 221 nncnd xJy0a=2yxy=supk0|2ka0<a
223 137 adantr xJy0a=2yxy=supk0|2ka0<x
224 223 nncnd xJy0a=2yxy=supk0|2ka0<x
225 nnexpcl 2y02y
226 3 225 mpan y02y
227 226 nncnd y02y
228 226 nnne0d y02y0
229 227 228 jca y02y2y0
230 229 ad3antlr xJy0a=2yxy=supk0|2ka0<2y2y0
231 divmul2 ax2y2y0a2y=xa=2yx
232 222 224 230 231 syl3anc xJy0a=2yxy=supk0|2ka0<a2y=xa=2yx
233 220 232 mpbird xJy0a=2yxy=supk0|2ka0<a2y=x
234 simpr xJy0a=2yxy=supk0|2ka0<y=supk0|2ka0<
235 234 oveq2d xJy0a=2yxy=supk0|2ka0<2y=2supk0|2ka0<
236 235 oveq2d xJy0a=2yxy=supk0|2ka0<a2y=a2supk0|2ka0<
237 233 236 eqtr3d xJy0a=2yxy=supk0|2ka0<x=a2supk0|2ka0<
238 237 ex xJy0a=2yxy=supk0|2ka0<x=a2supk0|2ka0<
239 219 238 jcai xJy0a=2yxy=supk0|2ka0<x=a2supk0|2ka0<
240 239 ancomd xJy0a=2yxx=a2supk0|2ka0<y=supk0|2ka0<
241 139 240 jca xJy0a=2yxax=a2supk0|2ka0<y=supk0|2ka0<
242 simprl ax=a2supk0|2ka0<y=supk0|2ka0<x=a2supk0|2ka0<
243 129 adantr ax=a2supk0|2ka0<y=supk0|2ka0<a2supk0|2ka0<J
244 242 243 eqeltrd ax=a2supk0|2ka0<y=supk0|2ka0<xJ
245 simprr ax=a2supk0|2ka0<y=supk0|2ka0<y=supk0|2ka0<
246 53 adantr ax=a2supk0|2ka0<y=supk0|2ka0<supk0|2ka0<0
247 245 246 eqeltrd ax=a2supk0|2ka0<y=supk0|2ka0<y0
248 117 adantr ax=a2supk0|2ka0<y=supk0|2ka0<a=2supk0|2ka0<a2supk0|2ka0<
249 245 oveq2d ax=a2supk0|2ka0<y=supk0|2ka0<2y=2supk0|2ka0<
250 249 242 oveq12d ax=a2supk0|2ka0<y=supk0|2ka0<2yx=2supk0|2ka0<a2supk0|2ka0<
251 248 250 eqtr4d ax=a2supk0|2ka0<y=supk0|2ka0<a=2yx
252 244 247 251 jca31 ax=a2supk0|2ka0<y=supk0|2ka0<xJy0a=2yx
253 241 252 impbii xJy0a=2yxax=a2supk0|2ka0<y=supk0|2ka0<
254 253 a1i xJy0a=2yxax=a2supk0|2ka0<y=supk0|2ka0<
255 2 13 131 254 f1od2 F:J×01-1 onto
256 255 mptru F:J×01-1 onto