viernes, 24 de marzo de 2017

1065. Staircase numbers

    Pepe Chapuzas was talking on powers of two... 

    Dear Taecher:
    a) Powers of two appear in the chessboard problem and the number of wheat grains. Do you remember?
2= 1
2= 2
2= 4
2= 8
2= 16
2= 32
2= 64
...

    b) With only two symbols we can write all the numbers! The binary (or base-two) numeral system is a positional notation as well as our decimal numeral system but with only two different bit figures (0 and 1) instead our ten digit figures. The bit 1 represents a power of two (1, 2, 4, 8, 16, 32, 64, ...) according to its position in the binary number, from the rightmost place to the leftmost place...

    c) For great powers of two we have some prefixes. Be careful because, strictly, 1 kibi > 1 kilo.


1 kibi = 210 = 1024   >   1 kilo = 103 = 1000
1 mebi = 220 = 1048576   >   1 mega = 106 = 1000000
1 gibi = 230 = 1073741824   >   1 giga = 109 = 1000000000

    d) A natural number can be written as a sum of two or more consecutive natural numbers if and only if it is not a power of two... These naturals are known as staircase numbers (also trapezoidal numbers or polite numbers). Powers of two were impolite!

    I interrupted Pepe. Item d) needed a detailed explanation... If that was true... what made powers of two so quirky? Pepe went on...

    Dear Teacher:
    There are two kinds of natural numbers: A natural can be either a power of two or a staircase number, but not both at the same time... So, 15 is not a power of two and it is a staircase number because it is a sum of consecutive naturals (and to top it off in two ways):


15  =  4 + 5 + 6  =  7 + 8

     Why 16 cannot be a staircase number? The answer is amazing: because 16 has no odd divisors! (We don't consider the number 1 as a divisor here now.) A natural number is a power of two if and only if has no odd divisors because the number 2 is the only even prime, is it not? I'll prove that powers of two cannot be staircase numbers by showing that every staircase number has at least one odd divisor...

    The staircase number  a+...+b  (a<b) is an arithmetic progression with  b–a+1  terms. So,


a+...+b = (a+b)·(b–a+1):2


    Hence either  a+b  or  b–a+1  is an odd divisor (and greater than 1).

    I'll prove now that if a natural number is not a power of two then it is a staircase number.

    If  n  is not a power of two, it has an odd divisor  k . Also  k2  is odd and there are two cases: either  k2 < 2n  or  k2 > 2n.

    If  k2 < 2n  then  n:k > k:2 , and the number  n = a+...+b , with  a = n:k–k:2+1:2  and  b = n:k+k:21:2 , is a staircase number with  k  addends (steps).

b–a+1 = n:k+k:2–1:2–n:k+k:2–1:2+1 = k
(a+b)(b–a+1):2 = (n:k–k:2+1:2+n:k+k:2–1:2)·k:2 = n

    If  k2 > 2n  then  k:2 > n:k , and the number  n = a+...+b , with  a = k:2–n:k+1:2  and  b = k:2+n:k–1:2 , is a staircase number with  2n:k  addends (steps).


b–a+1 = k:2+n:k–1:2–k:2+n:k–1:2+1 = 2n:k
(a+b)(b–a+1):2 = (k:2–n:k+1:2+k:2+n:k–1:2)·2n:k:2 = n

    To finish I ordered to write 6464 as a staircase number. Nina Guindilla did it:

    Dear Teacher:
    Since  101= 10201  <  2·6464 = 13938 , then


a = 6464:101–101:2+1:2 = 14
b = 6464:101+101:2–1:2 = 114
and
6464 = 14+15+16+17+...+114

No hay comentarios:

Publicar un comentario