![]() |
Mathbox for Alexander van der Vekens |
< Previous
Next >
Nearby theorems |
|
Mirrors > Home > MPE Home > Th. List > Mathboxes > blengt1fldiv2p1 | Structured version Visualization version GIF version |
Description: The binary length of an integer greater than 1 is the binary length of the integer divided by 2, increased by one. (Contributed by AV, 3-Jun-2020.) |
Ref | Expression |
---|---|
blengt1fldiv2p1 | ⊢ (𝑁 ∈ (ℤ≥‘2) → (#b‘𝑁) = ((#b‘(⌊‘(𝑁 / 2))) + 1)) |
Step | Hyp | Ref | Expression |
---|---|---|---|
1 | eluz2nn 12091 | . . 3 ⊢ (𝑁 ∈ (ℤ≥‘2) → 𝑁 ∈ ℕ) | |
2 | nneop 43894 | . . 3 ⊢ (𝑁 ∈ ℕ → ((𝑁 / 2) ∈ ℕ ∨ ((𝑁 + 1) / 2) ∈ ℕ)) | |
3 | 1, 2 | syl 17 | . 2 ⊢ (𝑁 ∈ (ℤ≥‘2) → ((𝑁 / 2) ∈ ℕ ∨ ((𝑁 + 1) / 2) ∈ ℕ)) |
4 | nnnn0 11708 | . . . . . . . . 9 ⊢ ((𝑁 / 2) ∈ ℕ → (𝑁 / 2) ∈ ℕ0) | |
5 | blennn0em1 43959 | . . . . . . . . 9 ⊢ ((𝑁 ∈ ℕ ∧ (𝑁 / 2) ∈ ℕ0) → (#b‘(𝑁 / 2)) = ((#b‘𝑁) − 1)) | |
6 | 4, 5 | sylan2 583 | . . . . . . . 8 ⊢ ((𝑁 ∈ ℕ ∧ (𝑁 / 2) ∈ ℕ) → (#b‘(𝑁 / 2)) = ((#b‘𝑁) − 1)) |
7 | 6 | ancoms 451 | . . . . . . 7 ⊢ (((𝑁 / 2) ∈ ℕ ∧ 𝑁 ∈ ℕ) → (#b‘(𝑁 / 2)) = ((#b‘𝑁) − 1)) |
8 | 7 | oveq1d 6985 | . . . . . 6 ⊢ (((𝑁 / 2) ∈ ℕ ∧ 𝑁 ∈ ℕ) → ((#b‘(𝑁 / 2)) + 1) = (((#b‘𝑁) − 1) + 1)) |
9 | nnz 11810 | . . . . . . . . . . 11 ⊢ ((𝑁 / 2) ∈ ℕ → (𝑁 / 2) ∈ ℤ) | |
10 | flid 12986 | . . . . . . . . . . 11 ⊢ ((𝑁 / 2) ∈ ℤ → (⌊‘(𝑁 / 2)) = (𝑁 / 2)) | |
11 | 9, 10 | syl 17 | . . . . . . . . . 10 ⊢ ((𝑁 / 2) ∈ ℕ → (⌊‘(𝑁 / 2)) = (𝑁 / 2)) |
12 | 11 | eqcomd 2778 | . . . . . . . . 9 ⊢ ((𝑁 / 2) ∈ ℕ → (𝑁 / 2) = (⌊‘(𝑁 / 2))) |
13 | 12 | fveq2d 6497 | . . . . . . . 8 ⊢ ((𝑁 / 2) ∈ ℕ → (#b‘(𝑁 / 2)) = (#b‘(⌊‘(𝑁 / 2)))) |
14 | 13 | oveq1d 6985 | . . . . . . 7 ⊢ ((𝑁 / 2) ∈ ℕ → ((#b‘(𝑁 / 2)) + 1) = ((#b‘(⌊‘(𝑁 / 2))) + 1)) |
15 | 14 | adantr 473 | . . . . . 6 ⊢ (((𝑁 / 2) ∈ ℕ ∧ 𝑁 ∈ ℕ) → ((#b‘(𝑁 / 2)) + 1) = ((#b‘(⌊‘(𝑁 / 2))) + 1)) |
16 | blennnelnn 43944 | . . . . . . . . 9 ⊢ (𝑁 ∈ ℕ → (#b‘𝑁) ∈ ℕ) | |
17 | 16 | nncnd 11449 | . . . . . . . 8 ⊢ (𝑁 ∈ ℕ → (#b‘𝑁) ∈ ℂ) |
18 | npcan1 10858 | . . . . . . . 8 ⊢ ((#b‘𝑁) ∈ ℂ → (((#b‘𝑁) − 1) + 1) = (#b‘𝑁)) | |
19 | 17, 18 | syl 17 | . . . . . . 7 ⊢ (𝑁 ∈ ℕ → (((#b‘𝑁) − 1) + 1) = (#b‘𝑁)) |
20 | 19 | adantl 474 | . . . . . 6 ⊢ (((𝑁 / 2) ∈ ℕ ∧ 𝑁 ∈ ℕ) → (((#b‘𝑁) − 1) + 1) = (#b‘𝑁)) |
21 | 8, 15, 20 | 3eqtr3rd 2817 | . . . . 5 ⊢ (((𝑁 / 2) ∈ ℕ ∧ 𝑁 ∈ ℕ) → (#b‘𝑁) = ((#b‘(⌊‘(𝑁 / 2))) + 1)) |
22 | 21 | expcom 406 | . . . 4 ⊢ (𝑁 ∈ ℕ → ((𝑁 / 2) ∈ ℕ → (#b‘𝑁) = ((#b‘(⌊‘(𝑁 / 2))) + 1))) |
23 | 22, 1 | syl11 33 | . . 3 ⊢ ((𝑁 / 2) ∈ ℕ → (𝑁 ∈ (ℤ≥‘2) → (#b‘𝑁) = ((#b‘(⌊‘(𝑁 / 2))) + 1))) |
24 | nnnn0 11708 | . . . . . . 7 ⊢ (((𝑁 + 1) / 2) ∈ ℕ → ((𝑁 + 1) / 2) ∈ ℕ0) | |
25 | blennngt2o2 43960 | . . . . . . 7 ⊢ ((𝑁 ∈ (ℤ≥‘2) ∧ ((𝑁 + 1) / 2) ∈ ℕ0) → (#b‘𝑁) = ((#b‘((𝑁 − 1) / 2)) + 1)) | |
26 | 24, 25 | sylan2 583 | . . . . . 6 ⊢ ((𝑁 ∈ (ℤ≥‘2) ∧ ((𝑁 + 1) / 2) ∈ ℕ) → (#b‘𝑁) = ((#b‘((𝑁 − 1) / 2)) + 1)) |
27 | 26 | ancoms 451 | . . . . 5 ⊢ ((((𝑁 + 1) / 2) ∈ ℕ ∧ 𝑁 ∈ (ℤ≥‘2)) → (#b‘𝑁) = ((#b‘((𝑁 − 1) / 2)) + 1)) |
28 | eluzge2nn0 12094 | . . . . . . . . 9 ⊢ (𝑁 ∈ (ℤ≥‘2) → 𝑁 ∈ ℕ0) | |
29 | nn0ofldiv2 43900 | . . . . . . . . 9 ⊢ ((𝑁 ∈ ℕ0 ∧ ((𝑁 + 1) / 2) ∈ ℕ0) → (⌊‘(𝑁 / 2)) = ((𝑁 − 1) / 2)) | |
30 | 28, 24, 29 | syl2anr 587 | . . . . . . . 8 ⊢ ((((𝑁 + 1) / 2) ∈ ℕ ∧ 𝑁 ∈ (ℤ≥‘2)) → (⌊‘(𝑁 / 2)) = ((𝑁 − 1) / 2)) |
31 | 30 | eqcomd 2778 | . . . . . . 7 ⊢ ((((𝑁 + 1) / 2) ∈ ℕ ∧ 𝑁 ∈ (ℤ≥‘2)) → ((𝑁 − 1) / 2) = (⌊‘(𝑁 / 2))) |
32 | 31 | fveq2d 6497 | . . . . . 6 ⊢ ((((𝑁 + 1) / 2) ∈ ℕ ∧ 𝑁 ∈ (ℤ≥‘2)) → (#b‘((𝑁 − 1) / 2)) = (#b‘(⌊‘(𝑁 / 2)))) |
33 | 32 | oveq1d 6985 | . . . . 5 ⊢ ((((𝑁 + 1) / 2) ∈ ℕ ∧ 𝑁 ∈ (ℤ≥‘2)) → ((#b‘((𝑁 − 1) / 2)) + 1) = ((#b‘(⌊‘(𝑁 / 2))) + 1)) |
34 | 27, 33 | eqtrd 2808 | . . . 4 ⊢ ((((𝑁 + 1) / 2) ∈ ℕ ∧ 𝑁 ∈ (ℤ≥‘2)) → (#b‘𝑁) = ((#b‘(⌊‘(𝑁 / 2))) + 1)) |
35 | 34 | ex 405 | . . 3 ⊢ (((𝑁 + 1) / 2) ∈ ℕ → (𝑁 ∈ (ℤ≥‘2) → (#b‘𝑁) = ((#b‘(⌊‘(𝑁 / 2))) + 1))) |
36 | 23, 35 | jaoi 843 | . 2 ⊢ (((𝑁 / 2) ∈ ℕ ∨ ((𝑁 + 1) / 2) ∈ ℕ) → (𝑁 ∈ (ℤ≥‘2) → (#b‘𝑁) = ((#b‘(⌊‘(𝑁 / 2))) + 1))) |
37 | 3, 36 | mpcom 38 | 1 ⊢ (𝑁 ∈ (ℤ≥‘2) → (#b‘𝑁) = ((#b‘(⌊‘(𝑁 / 2))) + 1)) |
Colors of variables: wff setvar class |
Syntax hints: → wi 4 ∧ wa 387 ∨ wo 833 = wceq 1507 ∈ wcel 2048 ‘cfv 6182 (class class class)co 6970 ℂcc 10325 1c1 10328 + caddc 10330 − cmin 10662 / cdiv 11090 ℕcn 11431 2c2 11488 ℕ0cn0 11700 ℤcz 11786 ℤ≥cuz 12051 ⌊cfl 12968 #bcblen 43937 |
This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1758 ax-4 1772 ax-5 1869 ax-6 1928 ax-7 1964 ax-8 2050 ax-9 2057 ax-10 2077 ax-11 2091 ax-12 2104 ax-13 2299 ax-ext 2745 ax-rep 5043 ax-sep 5054 ax-nul 5061 ax-pow 5113 ax-pr 5180 ax-un 7273 ax-inf2 8890 ax-cnex 10383 ax-resscn 10384 ax-1cn 10385 ax-icn 10386 ax-addcl 10387 ax-addrcl 10388 ax-mulcl 10389 ax-mulrcl 10390 ax-mulcom 10391 ax-addass 10392 ax-mulass 10393 ax-distr 10394 ax-i2m1 10395 ax-1ne0 10396 ax-1rid 10397 ax-rnegex 10398 ax-rrecex 10399 ax-cnre 10400 ax-pre-lttri 10401 ax-pre-lttrn 10402 ax-pre-ltadd 10403 ax-pre-mulgt0 10404 ax-pre-sup 10405 ax-addf 10406 ax-mulf 10407 |
This theorem depends on definitions: df-bi 199 df-an 388 df-or 834 df-3or 1069 df-3an 1070 df-tru 1510 df-fal 1520 df-ex 1743 df-nf 1747 df-sb 2014 df-mo 2544 df-eu 2580 df-clab 2754 df-cleq 2765 df-clel 2840 df-nfc 2912 df-ne 2962 df-nel 3068 df-ral 3087 df-rex 3088 df-reu 3089 df-rmo 3090 df-rab 3091 df-v 3411 df-sbc 3678 df-csb 3783 df-dif 3828 df-un 3830 df-in 3832 df-ss 3839 df-pss 3841 df-nul 4174 df-if 4345 df-pw 4418 df-sn 4436 df-pr 4438 df-tp 4440 df-op 4442 df-uni 4707 df-int 4744 df-iun 4788 df-iin 4789 df-br 4924 df-opab 4986 df-mpt 5003 df-tr 5025 df-id 5305 df-eprel 5310 df-po 5319 df-so 5320 df-fr 5359 df-se 5360 df-we 5361 df-xp 5406 df-rel 5407 df-cnv 5408 df-co 5409 df-dm 5410 df-rn 5411 df-res 5412 df-ima 5413 df-pred 5980 df-ord 6026 df-on 6027 df-lim 6028 df-suc 6029 df-iota 6146 df-fun 6184 df-fn 6185 df-f 6186 df-f1 6187 df-fo 6188 df-f1o 6189 df-fv 6190 df-isom 6191 df-riota 6931 df-ov 6973 df-oprab 6974 df-mpo 6975 df-of 7221 df-om 7391 df-1st 7494 df-2nd 7495 df-supp 7627 df-wrecs 7743 df-recs 7805 df-rdg 7843 df-1o 7897 df-2o 7898 df-oadd 7901 df-er 8081 df-map 8200 df-pm 8201 df-ixp 8252 df-en 8299 df-dom 8300 df-sdom 8301 df-fin 8302 df-fsupp 8621 df-fi 8662 df-sup 8693 df-inf 8694 df-oi 8761 df-card 9154 df-cda 9380 df-pnf 10468 df-mnf 10469 df-xr 10470 df-ltxr 10471 df-le 10472 df-sub 10664 df-neg 10665 df-div 11091 df-nn 11432 df-2 11496 df-3 11497 df-4 11498 df-5 11499 df-6 11500 df-7 11501 df-8 11502 df-9 11503 df-n0 11701 df-z 11787 df-dec 11905 df-uz 12052 df-q 12156 df-rp 12198 df-xneg 12317 df-xadd 12318 df-xmul 12319 df-ioo 12551 df-ioc 12552 df-ico 12553 df-icc 12554 df-fz 12702 df-fzo 12843 df-fl 12970 df-mod 13046 df-seq 13178 df-exp 13238 df-fac 13442 df-bc 13471 df-hash 13499 df-shft 14277 df-cj 14309 df-re 14310 df-im 14311 df-sqrt 14445 df-abs 14446 df-limsup 14679 df-clim 14696 df-rlim 14697 df-sum 14894 df-ef 15271 df-sin 15273 df-cos 15274 df-pi 15276 df-struct 16331 df-ndx 16332 df-slot 16333 df-base 16335 df-sets 16336 df-ress 16337 df-plusg 16424 df-mulr 16425 df-starv 16426 df-sca 16427 df-vsca 16428 df-ip 16429 df-tset 16430 df-ple 16431 df-ds 16433 df-unif 16434 df-hom 16435 df-cco 16436 df-rest 16542 df-topn 16543 df-0g 16561 df-gsum 16562 df-topgen 16563 df-pt 16564 df-prds 16567 df-xrs 16621 df-qtop 16626 df-imas 16627 df-xps 16629 df-mre 16705 df-mrc 16706 df-acs 16708 df-mgm 17700 df-sgrp 17742 df-mnd 17753 df-submnd 17794 df-mulg 18002 df-cntz 18208 df-cmn 18658 df-psmet 20229 df-xmet 20230 df-met 20231 df-bl 20232 df-mopn 20233 df-fbas 20234 df-fg 20235 df-cnfld 20238 df-top 21196 df-topon 21213 df-topsp 21235 df-bases 21248 df-cld 21321 df-ntr 21322 df-cls 21323 df-nei 21400 df-lp 21438 df-perf 21439 df-cn 21529 df-cnp 21530 df-haus 21617 df-tx 21864 df-hmeo 22057 df-fil 22148 df-fm 22240 df-flim 22241 df-flf 22242 df-xms 22623 df-ms 22624 df-tms 22625 df-cncf 23179 df-limc 24157 df-dv 24158 df-log 24831 df-cxp 24832 df-logb 25034 df-blen 43938 |
This theorem is referenced by: (None) |
Copyright terms: Public domain | W3C validator |