![]() |
Mathbox for Alexander van der Vekens |
< Previous
Next >
Nearby theorems |
|
Mirrors > Home > MPE Home > Th. List > Mathboxes > blennngt2o2 | Structured version Visualization version GIF version |
Description: The binary length of an odd integer greater than 1 is the binary length of the half of the integer decreased by 1, increased by 1. (Contributed by AV, 3-Jun-2020.) |
Ref | Expression |
---|---|
blennngt2o2 | ⊢ ((𝑁 ∈ (ℤ≥‘2) ∧ ((𝑁 + 1) / 2) ∈ ℕ0) → (#b‘𝑁) = ((#b‘((𝑁 − 1) / 2)) + 1)) |
Step | Hyp | Ref | Expression |
---|---|---|---|
1 | 2rp 12078 | . . . . . . . 8 ⊢ 2 ∈ ℝ+ | |
2 | 1ne2 11527 | . . . . . . . . 9 ⊢ 1 ≠ 2 | |
3 | 2 | necomi 3026 | . . . . . . . 8 ⊢ 2 ≠ 1 |
4 | eldifsn 4507 | . . . . . . . 8 ⊢ (2 ∈ (ℝ+ ∖ {1}) ↔ (2 ∈ ℝ+ ∧ 2 ≠ 1)) | |
5 | 1, 3, 4 | mpbir2an 703 | . . . . . . 7 ⊢ 2 ∈ (ℝ+ ∖ {1}) |
6 | uz2m1nn 12007 | . . . . . . . . 9 ⊢ (𝑁 ∈ (ℤ≥‘2) → (𝑁 − 1) ∈ ℕ) | |
7 | 6 | nnrpd 12114 | . . . . . . . 8 ⊢ (𝑁 ∈ (ℤ≥‘2) → (𝑁 − 1) ∈ ℝ+) |
8 | 7 | adantr 473 | . . . . . . 7 ⊢ ((𝑁 ∈ (ℤ≥‘2) ∧ ((𝑁 + 1) / 2) ∈ ℕ0) → (𝑁 − 1) ∈ ℝ+) |
9 | relogbdivb 43150 | . . . . . . 7 ⊢ ((2 ∈ (ℝ+ ∖ {1}) ∧ (𝑁 − 1) ∈ ℝ+) → (2 logb ((𝑁 − 1) / 2)) = ((2 logb (𝑁 − 1)) − 1)) | |
10 | 5, 8, 9 | sylancr 582 | . . . . . 6 ⊢ ((𝑁 ∈ (ℤ≥‘2) ∧ ((𝑁 + 1) / 2) ∈ ℕ0) → (2 logb ((𝑁 − 1) / 2)) = ((2 logb (𝑁 − 1)) − 1)) |
11 | 10 | fveq2d 6416 | . . . . 5 ⊢ ((𝑁 ∈ (ℤ≥‘2) ∧ ((𝑁 + 1) / 2) ∈ ℕ0) → (⌊‘(2 logb ((𝑁 − 1) / 2))) = (⌊‘((2 logb (𝑁 − 1)) − 1))) |
12 | 11 | oveq1d 6894 | . . . 4 ⊢ ((𝑁 ∈ (ℤ≥‘2) ∧ ((𝑁 + 1) / 2) ∈ ℕ0) → ((⌊‘(2 logb ((𝑁 − 1) / 2))) + 1) = ((⌊‘((2 logb (𝑁 − 1)) − 1)) + 1)) |
13 | 1 | a1i 11 | . . . . . . . . 9 ⊢ (𝑁 ∈ (ℤ≥‘2) → 2 ∈ ℝ+) |
14 | 3 | a1i 11 | . . . . . . . . 9 ⊢ (𝑁 ∈ (ℤ≥‘2) → 2 ≠ 1) |
15 | relogbcl 24854 | . . . . . . . . 9 ⊢ ((2 ∈ ℝ+ ∧ (𝑁 − 1) ∈ ℝ+ ∧ 2 ≠ 1) → (2 logb (𝑁 − 1)) ∈ ℝ) | |
16 | 13, 7, 14, 15 | syl3anc 1491 | . . . . . . . 8 ⊢ (𝑁 ∈ (ℤ≥‘2) → (2 logb (𝑁 − 1)) ∈ ℝ) |
17 | 1z 11696 | . . . . . . . 8 ⊢ 1 ∈ ℤ | |
18 | 16, 17 | jctir 517 | . . . . . . 7 ⊢ (𝑁 ∈ (ℤ≥‘2) → ((2 logb (𝑁 − 1)) ∈ ℝ ∧ 1 ∈ ℤ)) |
19 | 18 | adantr 473 | . . . . . 6 ⊢ ((𝑁 ∈ (ℤ≥‘2) ∧ ((𝑁 + 1) / 2) ∈ ℕ0) → ((2 logb (𝑁 − 1)) ∈ ℝ ∧ 1 ∈ ℤ)) |
20 | flsubz 43106 | . . . . . 6 ⊢ (((2 logb (𝑁 − 1)) ∈ ℝ ∧ 1 ∈ ℤ) → (⌊‘((2 logb (𝑁 − 1)) − 1)) = ((⌊‘(2 logb (𝑁 − 1))) − 1)) | |
21 | 19, 20 | syl 17 | . . . . 5 ⊢ ((𝑁 ∈ (ℤ≥‘2) ∧ ((𝑁 + 1) / 2) ∈ ℕ0) → (⌊‘((2 logb (𝑁 − 1)) − 1)) = ((⌊‘(2 logb (𝑁 − 1))) − 1)) |
22 | 21 | oveq1d 6894 | . . . 4 ⊢ ((𝑁 ∈ (ℤ≥‘2) ∧ ((𝑁 + 1) / 2) ∈ ℕ0) → ((⌊‘((2 logb (𝑁 − 1)) − 1)) + 1) = (((⌊‘(2 logb (𝑁 − 1))) − 1) + 1)) |
23 | 16 | flcld 12853 | . . . . . . . 8 ⊢ (𝑁 ∈ (ℤ≥‘2) → (⌊‘(2 logb (𝑁 − 1))) ∈ ℤ) |
24 | 23 | zcnd 11772 | . . . . . . 7 ⊢ (𝑁 ∈ (ℤ≥‘2) → (⌊‘(2 logb (𝑁 − 1))) ∈ ℂ) |
25 | npcan1 10748 | . . . . . . 7 ⊢ ((⌊‘(2 logb (𝑁 − 1))) ∈ ℂ → (((⌊‘(2 logb (𝑁 − 1))) − 1) + 1) = (⌊‘(2 logb (𝑁 − 1)))) | |
26 | 24, 25 | syl 17 | . . . . . 6 ⊢ (𝑁 ∈ (ℤ≥‘2) → (((⌊‘(2 logb (𝑁 − 1))) − 1) + 1) = (⌊‘(2 logb (𝑁 − 1)))) |
27 | 26 | adantr 473 | . . . . 5 ⊢ ((𝑁 ∈ (ℤ≥‘2) ∧ ((𝑁 + 1) / 2) ∈ ℕ0) → (((⌊‘(2 logb (𝑁 − 1))) − 1) + 1) = (⌊‘(2 logb (𝑁 − 1)))) |
28 | eluz2nn 11969 | . . . . . . . . . . 11 ⊢ (𝑁 ∈ (ℤ≥‘2) → 𝑁 ∈ ℕ) | |
29 | 28 | peano2nnd 11332 | . . . . . . . . . 10 ⊢ (𝑁 ∈ (ℤ≥‘2) → (𝑁 + 1) ∈ ℕ) |
30 | 29 | nnred 11330 | . . . . . . . . 9 ⊢ (𝑁 ∈ (ℤ≥‘2) → (𝑁 + 1) ∈ ℝ) |
31 | 2re 11386 | . . . . . . . . . 10 ⊢ 2 ∈ ℝ | |
32 | 31 | a1i 11 | . . . . . . . . 9 ⊢ (𝑁 ∈ (ℤ≥‘2) → 2 ∈ ℝ) |
33 | eluzge2nn0 11970 | . . . . . . . . . 10 ⊢ (𝑁 ∈ (ℤ≥‘2) → 𝑁 ∈ ℕ0) | |
34 | nn0p1gt0 11610 | . . . . . . . . . 10 ⊢ (𝑁 ∈ ℕ0 → 0 < (𝑁 + 1)) | |
35 | 33, 34 | syl 17 | . . . . . . . . 9 ⊢ (𝑁 ∈ (ℤ≥‘2) → 0 < (𝑁 + 1)) |
36 | 2pos 11422 | . . . . . . . . . 10 ⊢ 0 < 2 | |
37 | 36 | a1i 11 | . . . . . . . . 9 ⊢ (𝑁 ∈ (ℤ≥‘2) → 0 < 2) |
38 | 30, 32, 35, 37 | divgt0d 11252 | . . . . . . . 8 ⊢ (𝑁 ∈ (ℤ≥‘2) → 0 < ((𝑁 + 1) / 2)) |
39 | nn0z 11689 | . . . . . . . 8 ⊢ (((𝑁 + 1) / 2) ∈ ℕ0 → ((𝑁 + 1) / 2) ∈ ℤ) | |
40 | 38, 39 | anim12ci 608 | . . . . . . 7 ⊢ ((𝑁 ∈ (ℤ≥‘2) ∧ ((𝑁 + 1) / 2) ∈ ℕ0) → (((𝑁 + 1) / 2) ∈ ℤ ∧ 0 < ((𝑁 + 1) / 2))) |
41 | elnnz 11675 | . . . . . . 7 ⊢ (((𝑁 + 1) / 2) ∈ ℕ ↔ (((𝑁 + 1) / 2) ∈ ℤ ∧ 0 < ((𝑁 + 1) / 2))) | |
42 | 40, 41 | sylibr 226 | . . . . . 6 ⊢ ((𝑁 ∈ (ℤ≥‘2) ∧ ((𝑁 + 1) / 2) ∈ ℕ0) → ((𝑁 + 1) / 2) ∈ ℕ) |
43 | nnolog2flm1 43178 | . . . . . 6 ⊢ ((𝑁 ∈ (ℤ≥‘2) ∧ ((𝑁 + 1) / 2) ∈ ℕ) → (⌊‘(2 logb 𝑁)) = (⌊‘(2 logb (𝑁 − 1)))) | |
44 | 42, 43 | syldan 586 | . . . . 5 ⊢ ((𝑁 ∈ (ℤ≥‘2) ∧ ((𝑁 + 1) / 2) ∈ ℕ0) → (⌊‘(2 logb 𝑁)) = (⌊‘(2 logb (𝑁 − 1)))) |
45 | 27, 44 | eqtr4d 2837 | . . . 4 ⊢ ((𝑁 ∈ (ℤ≥‘2) ∧ ((𝑁 + 1) / 2) ∈ ℕ0) → (((⌊‘(2 logb (𝑁 − 1))) − 1) + 1) = (⌊‘(2 logb 𝑁))) |
46 | 12, 22, 45 | 3eqtrd 2838 | . . 3 ⊢ ((𝑁 ∈ (ℤ≥‘2) ∧ ((𝑁 + 1) / 2) ∈ ℕ0) → ((⌊‘(2 logb ((𝑁 − 1) / 2))) + 1) = (⌊‘(2 logb 𝑁))) |
47 | 46 | oveq1d 6894 | . 2 ⊢ ((𝑁 ∈ (ℤ≥‘2) ∧ ((𝑁 + 1) / 2) ∈ ℕ0) → (((⌊‘(2 logb ((𝑁 − 1) / 2))) + 1) + 1) = ((⌊‘(2 logb 𝑁)) + 1)) |
48 | nno 15433 | . . 3 ⊢ ((𝑁 ∈ (ℤ≥‘2) ∧ ((𝑁 + 1) / 2) ∈ ℕ0) → ((𝑁 − 1) / 2) ∈ ℕ) | |
49 | blennn 43163 | . . . 4 ⊢ (((𝑁 − 1) / 2) ∈ ℕ → (#b‘((𝑁 − 1) / 2)) = ((⌊‘(2 logb ((𝑁 − 1) / 2))) + 1)) | |
50 | 49 | oveq1d 6894 | . . 3 ⊢ (((𝑁 − 1) / 2) ∈ ℕ → ((#b‘((𝑁 − 1) / 2)) + 1) = (((⌊‘(2 logb ((𝑁 − 1) / 2))) + 1) + 1)) |
51 | 48, 50 | syl 17 | . 2 ⊢ ((𝑁 ∈ (ℤ≥‘2) ∧ ((𝑁 + 1) / 2) ∈ ℕ0) → ((#b‘((𝑁 − 1) / 2)) + 1) = (((⌊‘(2 logb ((𝑁 − 1) / 2))) + 1) + 1)) |
52 | blennn 43163 | . . . 4 ⊢ (𝑁 ∈ ℕ → (#b‘𝑁) = ((⌊‘(2 logb 𝑁)) + 1)) | |
53 | 28, 52 | syl 17 | . . 3 ⊢ (𝑁 ∈ (ℤ≥‘2) → (#b‘𝑁) = ((⌊‘(2 logb 𝑁)) + 1)) |
54 | 53 | adantr 473 | . 2 ⊢ ((𝑁 ∈ (ℤ≥‘2) ∧ ((𝑁 + 1) / 2) ∈ ℕ0) → (#b‘𝑁) = ((⌊‘(2 logb 𝑁)) + 1)) |
55 | 47, 51, 54 | 3eqtr4rd 2845 | 1 ⊢ ((𝑁 ∈ (ℤ≥‘2) ∧ ((𝑁 + 1) / 2) ∈ ℕ0) → (#b‘𝑁) = ((#b‘((𝑁 − 1) / 2)) + 1)) |
Colors of variables: wff setvar class |
Syntax hints: → wi 4 ∧ wa 385 = wceq 1653 ∈ wcel 2157 ≠ wne 2972 ∖ cdif 3767 {csn 4369 class class class wbr 4844 ‘cfv 6102 (class class class)co 6879 ℂcc 10223 ℝcr 10224 0cc0 10225 1c1 10226 + caddc 10228 < clt 10364 − cmin 10557 / cdiv 10977 ℕcn 11313 2c2 11367 ℕ0cn0 11579 ℤcz 11665 ℤ≥cuz 11929 ℝ+crp 12073 ⌊cfl 12845 logb clogb 24845 #bcblen 43157 |
This theorem was proved from axioms: ax-mp 5 ax-1 6 ax-2 7 ax-3 8 ax-gen 1891 ax-4 1905 ax-5 2006 ax-6 2072 ax-7 2107 ax-8 2159 ax-9 2166 ax-10 2185 ax-11 2200 ax-12 2213 ax-13 2378 ax-ext 2778 ax-rep 4965 ax-sep 4976 ax-nul 4984 ax-pow 5036 ax-pr 5098 ax-un 7184 ax-inf2 8789 ax-cnex 10281 ax-resscn 10282 ax-1cn 10283 ax-icn 10284 ax-addcl 10285 ax-addrcl 10286 ax-mulcl 10287 ax-mulrcl 10288 ax-mulcom 10289 ax-addass 10290 ax-mulass 10291 ax-distr 10292 ax-i2m1 10293 ax-1ne0 10294 ax-1rid 10295 ax-rnegex 10296 ax-rrecex 10297 ax-cnre 10298 ax-pre-lttri 10299 ax-pre-lttrn 10300 ax-pre-ltadd 10301 ax-pre-mulgt0 10302 ax-pre-sup 10303 ax-addf 10304 ax-mulf 10305 |
This theorem depends on definitions: df-bi 199 df-an 386 df-or 875 df-3or 1109 df-3an 1110 df-tru 1657 df-fal 1667 df-ex 1876 df-nf 1880 df-sb 2065 df-mo 2592 df-eu 2610 df-clab 2787 df-cleq 2793 df-clel 2796 df-nfc 2931 df-ne 2973 df-nel 3076 df-ral 3095 df-rex 3096 df-reu 3097 df-rmo 3098 df-rab 3099 df-v 3388 df-sbc 3635 df-csb 3730 df-dif 3773 df-un 3775 df-in 3777 df-ss 3784 df-pss 3786 df-nul 4117 df-if 4279 df-pw 4352 df-sn 4370 df-pr 4372 df-tp 4374 df-op 4376 df-uni 4630 df-int 4669 df-iun 4713 df-iin 4714 df-br 4845 df-opab 4907 df-mpt 4924 df-tr 4947 df-id 5221 df-eprel 5226 df-po 5234 df-so 5235 df-fr 5272 df-se 5273 df-we 5274 df-xp 5319 df-rel 5320 df-cnv 5321 df-co 5322 df-dm 5323 df-rn 5324 df-res 5325 df-ima 5326 df-pred 5899 df-ord 5945 df-on 5946 df-lim 5947 df-suc 5948 df-iota 6065 df-fun 6104 df-fn 6105 df-f 6106 df-f1 6107 df-fo 6108 df-f1o 6109 df-fv 6110 df-isom 6111 df-riota 6840 df-ov 6882 df-oprab 6883 df-mpt2 6884 df-of 7132 df-om 7301 df-1st 7402 df-2nd 7403 df-supp 7534 df-wrecs 7646 df-recs 7708 df-rdg 7746 df-1o 7800 df-2o 7801 df-oadd 7804 df-er 7983 df-map 8098 df-pm 8099 df-ixp 8150 df-en 8197 df-dom 8198 df-sdom 8199 df-fin 8200 df-fsupp 8519 df-fi 8560 df-sup 8591 df-inf 8592 df-oi 8658 df-card 9052 df-cda 9279 df-pnf 10366 df-mnf 10367 df-xr 10368 df-ltxr 10369 df-le 10370 df-sub 10559 df-neg 10560 df-div 10978 df-nn 11314 df-2 11375 df-3 11376 df-4 11377 df-5 11378 df-6 11379 df-7 11380 df-8 11381 df-9 11382 df-n0 11580 df-z 11666 df-dec 11783 df-uz 11930 df-q 12033 df-rp 12074 df-xneg 12192 df-xadd 12193 df-xmul 12194 df-ioo 12427 df-ioc 12428 df-ico 12429 df-icc 12430 df-fz 12580 df-fzo 12720 df-fl 12847 df-mod 12923 df-seq 13055 df-exp 13114 df-fac 13313 df-bc 13342 df-hash 13370 df-shft 14147 df-cj 14179 df-re 14180 df-im 14181 df-sqrt 14315 df-abs 14316 df-limsup 14542 df-clim 14559 df-rlim 14560 df-sum 14757 df-ef 15133 df-sin 15135 df-cos 15136 df-pi 15138 df-struct 16185 df-ndx 16186 df-slot 16187 df-base 16189 df-sets 16190 df-ress 16191 df-plusg 16279 df-mulr 16280 df-starv 16281 df-sca 16282 df-vsca 16283 df-ip 16284 df-tset 16285 df-ple 16286 df-ds 16288 df-unif 16289 df-hom 16290 df-cco 16291 df-rest 16397 df-topn 16398 df-0g 16416 df-gsum 16417 df-topgen 16418 df-pt 16419 df-prds 16422 df-xrs 16476 df-qtop 16481 df-imas 16482 df-xps 16484 df-mre 16560 df-mrc 16561 df-acs 16563 df-mgm 17556 df-sgrp 17598 df-mnd 17609 df-submnd 17650 df-mulg 17856 df-cntz 18061 df-cmn 18509 df-psmet 20059 df-xmet 20060 df-met 20061 df-bl 20062 df-mopn 20063 df-fbas 20064 df-fg 20065 df-cnfld 20068 df-top 21026 df-topon 21043 df-topsp 21065 df-bases 21078 df-cld 21151 df-ntr 21152 df-cls 21153 df-nei 21230 df-lp 21268 df-perf 21269 df-cn 21359 df-cnp 21360 df-haus 21447 df-tx 21693 df-hmeo 21886 df-fil 21977 df-fm 22069 df-flim 22070 df-flf 22071 df-xms 22452 df-ms 22453 df-tms 22454 df-cncf 23008 df-limc 23970 df-dv 23971 df-log 24643 df-cxp 24644 df-logb 24846 df-blen 43158 |
This theorem is referenced by: blengt1fldiv2p1 43181 nn0sumshdiglemB 43208 |
Copyright terms: Public domain | W3C validator |