![]() |
Mathbox for Alexander van der Vekens |
< Previous
Next >
Nearby theorems |
|
Mirrors > Home > MPE Home > Th. List > Mathboxes > blennnt2 | Structured version Visualization version GIF version |
Description: The binary length of a positive integer, doubled and increased by 1, is the binary length of the integer plus 1. (Contributed by AV, 30-May-2010.) |
Ref | Expression |
---|---|
blennnt2 | ⊢ (𝑁 ∈ ℕ → (#b‘(2 · 𝑁)) = ((#b‘𝑁) + 1)) |
Step | Hyp | Ref | Expression |
---|---|---|---|
1 | 2nn 11512 | . . . . 5 ⊢ 2 ∈ ℕ | |
2 | 1 | a1i 11 | . . . 4 ⊢ (𝑁 ∈ ℕ → 2 ∈ ℕ) |
3 | id 22 | . . . 4 ⊢ (𝑁 ∈ ℕ → 𝑁 ∈ ℕ) | |
4 | 2, 3 | nnmulcld 11492 | . . 3 ⊢ (𝑁 ∈ ℕ → (2 · 𝑁) ∈ ℕ) |
5 | blennn 44033 | . . 3 ⊢ ((2 · 𝑁) ∈ ℕ → (#b‘(2 · 𝑁)) = ((⌊‘(2 logb (2 · 𝑁))) + 1)) | |
6 | 4, 5 | syl 17 | . 2 ⊢ (𝑁 ∈ ℕ → (#b‘(2 · 𝑁)) = ((⌊‘(2 logb (2 · 𝑁))) + 1)) |
7 | 2cn 11514 | . . . . . . . . 9 ⊢ 2 ∈ ℂ | |
8 | 7 | a1i 11 | . . . . . . . 8 ⊢ (𝑁 ∈ ℕ → 2 ∈ ℂ) |
9 | nncn 11447 | . . . . . . . 8 ⊢ (𝑁 ∈ ℕ → 𝑁 ∈ ℂ) | |
10 | 8, 9 | mulcomd 10460 | . . . . . . 7 ⊢ (𝑁 ∈ ℕ → (2 · 𝑁) = (𝑁 · 2)) |
11 | 10 | oveq2d 6991 | . . . . . 6 ⊢ (𝑁 ∈ ℕ → (2 logb (2 · 𝑁)) = (2 logb (𝑁 · 2))) |
12 | 2z 11826 | . . . . . . . . 9 ⊢ 2 ∈ ℤ | |
13 | uzid 12072 | . . . . . . . . 9 ⊢ (2 ∈ ℤ → 2 ∈ (ℤ≥‘2)) | |
14 | 12, 13 | ax-mp 5 | . . . . . . . 8 ⊢ 2 ∈ (ℤ≥‘2) |
15 | eluz2cnn0n1 43964 | . . . . . . . 8 ⊢ (2 ∈ (ℤ≥‘2) → 2 ∈ (ℂ ∖ {0, 1})) | |
16 | 14, 15 | mp1i 13 | . . . . . . 7 ⊢ (𝑁 ∈ ℕ → 2 ∈ (ℂ ∖ {0, 1})) |
17 | nnrp 12216 | . . . . . . 7 ⊢ (𝑁 ∈ ℕ → 𝑁 ∈ ℝ+) | |
18 | 2rp 12208 | . . . . . . . 8 ⊢ 2 ∈ ℝ+ | |
19 | 18 | a1i 11 | . . . . . . 7 ⊢ (𝑁 ∈ ℕ → 2 ∈ ℝ+) |
20 | relogbmul 25072 | . . . . . . 7 ⊢ ((2 ∈ (ℂ ∖ {0, 1}) ∧ (𝑁 ∈ ℝ+ ∧ 2 ∈ ℝ+)) → (2 logb (𝑁 · 2)) = ((2 logb 𝑁) + (2 logb 2))) | |
21 | 16, 17, 19, 20 | syl12anc 825 | . . . . . 6 ⊢ (𝑁 ∈ ℕ → (2 logb (𝑁 · 2)) = ((2 logb 𝑁) + (2 logb 2))) |
22 | 2ne0 11550 | . . . . . . . . 9 ⊢ 2 ≠ 0 | |
23 | 1ne2 11654 | . . . . . . . . . 10 ⊢ 1 ≠ 2 | |
24 | 23 | necomi 3016 | . . . . . . . . 9 ⊢ 2 ≠ 1 |
25 | 7, 22, 24 | 3pm3.2i 1320 | . . . . . . . 8 ⊢ (2 ∈ ℂ ∧ 2 ≠ 0 ∧ 2 ≠ 1) |
26 | logbid1 25063 | . . . . . . . 8 ⊢ ((2 ∈ ℂ ∧ 2 ≠ 0 ∧ 2 ≠ 1) → (2 logb 2) = 1) | |
27 | 25, 26 | mp1i 13 | . . . . . . 7 ⊢ (𝑁 ∈ ℕ → (2 logb 2) = 1) |
28 | 27 | oveq2d 6991 | . . . . . 6 ⊢ (𝑁 ∈ ℕ → ((2 logb 𝑁) + (2 logb 2)) = ((2 logb 𝑁) + 1)) |
29 | 11, 21, 28 | 3eqtrd 2813 | . . . . 5 ⊢ (𝑁 ∈ ℕ → (2 logb (2 · 𝑁)) = ((2 logb 𝑁) + 1)) |
30 | 29 | fveq2d 6501 | . . . 4 ⊢ (𝑁 ∈ ℕ → (⌊‘(2 logb (2 · 𝑁))) = (⌊‘((2 logb 𝑁) + 1))) |
31 | 24 | a1i 11 | . . . . . 6 ⊢ (𝑁 ∈ ℕ → 2 ≠ 1) |
32 | relogbcl 25068 | . . . . . 6 ⊢ ((2 ∈ ℝ+ ∧ 𝑁 ∈ ℝ+ ∧ 2 ≠ 1) → (2 logb 𝑁) ∈ ℝ) | |
33 | 19, 17, 31, 32 | syl3anc 1352 | . . . . 5 ⊢ (𝑁 ∈ ℕ → (2 logb 𝑁) ∈ ℝ) |
34 | 1zzd 11825 | . . . . 5 ⊢ (𝑁 ∈ ℕ → 1 ∈ ℤ) | |
35 | fladdz 13009 | . . . . 5 ⊢ (((2 logb 𝑁) ∈ ℝ ∧ 1 ∈ ℤ) → (⌊‘((2 logb 𝑁) + 1)) = ((⌊‘(2 logb 𝑁)) + 1)) | |
36 | 33, 34, 35 | syl2anc 576 | . . . 4 ⊢ (𝑁 ∈ ℕ → (⌊‘((2 logb 𝑁) + 1)) = ((⌊‘(2 logb 𝑁)) + 1)) |
37 | 30, 36 | eqtrd 2809 | . . 3 ⊢ (𝑁 ∈ ℕ → (⌊‘(2 logb (2 · 𝑁))) = ((⌊‘(2 logb 𝑁)) + 1)) |
38 | 37 | oveq1d 6990 | . 2 ⊢ (𝑁 ∈ ℕ → ((⌊‘(2 logb (2 · 𝑁))) + 1) = (((⌊‘(2 logb 𝑁)) + 1) + 1)) |
39 | blennn 44033 | . . . 4 ⊢ (𝑁 ∈ ℕ → (#b‘𝑁) = ((⌊‘(2 logb 𝑁)) + 1)) | |
40 | 39 | eqcomd 2779 | . . 3 ⊢ (𝑁 ∈ ℕ → ((⌊‘(2 logb 𝑁)) + 1) = (#b‘𝑁)) |
41 | 40 | oveq1d 6990 | . 2 ⊢ (𝑁 ∈ ℕ → (((⌊‘(2 logb 𝑁)) + 1) + 1) = ((#b‘𝑁) + 1)) |
42 | 6, 38, 41 | 3eqtrd 2813 | 1 ⊢ (𝑁 ∈ ℕ → (#b‘(2 · 𝑁)) = ((#b‘𝑁) + 1)) |
Colors of variables: wff setvar class |
Syntax hints: → wi 4 ∧ w3a 1069 = wceq 1508 ∈ wcel 2051 ≠ wne 2962 ∖ cdif 3821 {cpr 4438 ‘cfv 6186 (class class class)co 6975 ℂcc 10332 ℝcr 10333 0cc0 10334 1c1 10335 + caddc 10337 · cmul 10339 ℕcn 11438 2c2 11494 ℤcz 11792 ℤ≥cuz 12057 ℝ+crp 12203 ⌊cfl 12974 logb clogb 25059 #bcblen 44027 |
This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1759 ax-4 1773 ax-5 1870 ax-6 1929 ax-7 1966 ax-8 2053 ax-9 2060 ax-10 2080 ax-11 2094 ax-12 2107 ax-13 2302 ax-ext 2745 ax-rep 5046 ax-sep 5057 ax-nul 5064 ax-pow 5116 ax-pr 5183 ax-un 7278 ax-inf2 8897 ax-cnex 10390 ax-resscn 10391 ax-1cn 10392 ax-icn 10393 ax-addcl 10394 ax-addrcl 10395 ax-mulcl 10396 ax-mulrcl 10397 ax-mulcom 10398 ax-addass 10399 ax-mulass 10400 ax-distr 10401 ax-i2m1 10402 ax-1ne0 10403 ax-1rid 10404 ax-rnegex 10405 ax-rrecex 10406 ax-cnre 10407 ax-pre-lttri 10408 ax-pre-lttrn 10409 ax-pre-ltadd 10410 ax-pre-mulgt0 10411 ax-pre-sup 10412 ax-addf 10413 ax-mulf 10414 |
This theorem depends on definitions: df-bi 199 df-an 388 df-or 835 df-3or 1070 df-3an 1071 df-tru 1511 df-fal 1521 df-ex 1744 df-nf 1748 df-sb 2017 df-mo 2548 df-eu 2585 df-clab 2754 df-cleq 2766 df-clel 2841 df-nfc 2913 df-ne 2963 df-nel 3069 df-ral 3088 df-rex 3089 df-reu 3090 df-rmo 3091 df-rab 3092 df-v 3412 df-sbc 3677 df-csb 3782 df-dif 3827 df-un 3829 df-in 3831 df-ss 3838 df-pss 3840 df-nul 4174 df-if 4346 df-pw 4419 df-sn 4437 df-pr 4439 df-tp 4441 df-op 4443 df-uni 4710 df-int 4747 df-iun 4791 df-iin 4792 df-br 4927 df-opab 4989 df-mpt 5006 df-tr 5028 df-id 5309 df-eprel 5314 df-po 5323 df-so 5324 df-fr 5363 df-se 5364 df-we 5365 df-xp 5410 df-rel 5411 df-cnv 5412 df-co 5413 df-dm 5414 df-rn 5415 df-res 5416 df-ima 5417 df-pred 5984 df-ord 6030 df-on 6031 df-lim 6032 df-suc 6033 df-iota 6150 df-fun 6188 df-fn 6189 df-f 6190 df-f1 6191 df-fo 6192 df-f1o 6193 df-fv 6194 df-isom 6195 df-riota 6936 df-ov 6978 df-oprab 6979 df-mpo 6980 df-of 7226 df-om 7396 df-1st 7500 df-2nd 7501 df-supp 7633 df-wrecs 7749 df-recs 7811 df-rdg 7849 df-1o 7904 df-2o 7905 df-oadd 7908 df-er 8088 df-map 8207 df-pm 8208 df-ixp 8259 df-en 8306 df-dom 8307 df-sdom 8308 df-fin 8309 df-fsupp 8628 df-fi 8669 df-sup 8700 df-inf 8701 df-oi 8768 df-card 9161 df-cda 9387 df-pnf 10475 df-mnf 10476 df-xr 10477 df-ltxr 10478 df-le 10479 df-sub 10671 df-neg 10672 df-div 11098 df-nn 11439 df-2 11502 df-3 11503 df-4 11504 df-5 11505 df-6 11506 df-7 11507 df-8 11508 df-9 11509 df-n0 11707 df-z 11793 df-dec 11911 df-uz 12058 df-q 12162 df-rp 12204 df-xneg 12323 df-xadd 12324 df-xmul 12325 df-ioo 12557 df-ioc 12558 df-ico 12559 df-icc 12560 df-fz 12708 df-fzo 12849 df-fl 12976 df-mod 13052 df-seq 13184 df-exp 13244 df-fac 13448 df-bc 13477 df-hash 13505 df-shft 14286 df-cj 14318 df-re 14319 df-im 14320 df-sqrt 14454 df-abs 14455 df-limsup 14688 df-clim 14705 df-rlim 14706 df-sum 14903 df-ef 15280 df-sin 15282 df-cos 15283 df-pi 15285 df-struct 16340 df-ndx 16341 df-slot 16342 df-base 16344 df-sets 16345 df-ress 16346 df-plusg 16433 df-mulr 16434 df-starv 16435 df-sca 16436 df-vsca 16437 df-ip 16438 df-tset 16439 df-ple 16440 df-ds 16442 df-unif 16443 df-hom 16444 df-cco 16445 df-rest 16551 df-topn 16552 df-0g 16570 df-gsum 16571 df-topgen 16572 df-pt 16573 df-prds 16576 df-xrs 16630 df-qtop 16635 df-imas 16636 df-xps 16638 df-mre 16728 df-mrc 16729 df-acs 16731 df-mgm 17723 df-sgrp 17765 df-mnd 17776 df-submnd 17817 df-mulg 18025 df-cntz 18231 df-cmn 18681 df-psmet 20255 df-xmet 20256 df-met 20257 df-bl 20258 df-mopn 20259 df-fbas 20260 df-fg 20261 df-cnfld 20264 df-top 21222 df-topon 21239 df-topsp 21261 df-bases 21274 df-cld 21347 df-ntr 21348 df-cls 21349 df-nei 21426 df-lp 21464 df-perf 21465 df-cn 21555 df-cnp 21556 df-haus 21643 df-tx 21890 df-hmeo 22083 df-fil 22174 df-fm 22266 df-flim 22267 df-flf 22268 df-xms 22649 df-ms 22650 df-tms 22651 df-cncf 23205 df-limc 24183 df-dv 24184 df-log 24857 df-logb 25060 df-blen 44028 |
This theorem is referenced by: blennn0em1 44049 |
Copyright terms: Public domain | W3C validator |