TIFR CSE 2012 | Part A | Question: 11

Question

Let $N$ be the sum of all numbers from $1$ to $1023$ except the five primes numbers: $2, 3, 11, 17, 31.$ Suppose all numbers are represented using two bytes (sixteen bits). What is the value of the least significant byte (the least significant eight bits) of $N$?

• A. $00000000$
• B. $10101110$
• C. $01000000$
• D. $10000000$
• E. $11000000$

Comments

Please contribute if someone has a better approach.

Answer 1

This is another way of saying , what will be the remainder when $N$ is divided by $\large 2{^8}=256$ ?

Here $N =1023\times \dfrac{1024}{2} - (2+3+11+17+31)$

       $= 1023\times 512 - 64$

      $= 1022\times 512 + (512-64)$

      $= 1022\times 512 + 448$

Now $448 \% 256 = 192 = 11000000$

So option e) is correct.

Comments

This is another way of saying , what will be the remainder when N is divided by 2^8=256?

How??

---

In binary representation last 8 bits represent mod 256. i.e., for 2^d,

n%(2^d) = n & (d-1);

---

N = 523712

and max number that can be represented using 16 bits = 65535

How can you directly go for mod ?

Still answer is coming out as (e) :D

But don' t we need to consider that @Arjun Sir?

---

Mod of 256 ranges from 0 to 255 i.e. mod values can be represented using 8 bits and these 8 bits come in the LSB.

256%256=0 so LSB=0 i.e. 00000001 00000000

257%256=1 so LSB=1 i.e. 00000001 00000001

511%256=255 so LSB=255 i.e. 00000001 11111111

And so on..

---

Please Explain

---

@Gupta731 

Just try for random number and take "mod 256" , this remainder will always be represented by these           8 LSB's.

Now, 1023*1024/2 = 523776 

now, 523776 - (2+3+11+17+31) = 523712

523712 mod 256 = 192

192 in binary => 11000000

---

sir what is the meaning of “ n & d-1 “

Answer 2

$N= \frac{1023(1023+1)}{2} – (2+3+11+17+31) = 1023 \times 512 – 64 = (2^{10} – 1)2^9 – 2^6$

$ N= 2^6((2^{10} – 1)2^3 – 1)$

$\text{$2^{10}$ – 1 has binary representation 0000000001111111111 (10 times 1s)}$

$\text{$(2^{10} – 1)2^3$ has binary representation 0000001111111111000}$

$\text{(shifted $3$ bits left because $2^3$ is multiplied)}$

$\text{$(2^{10} – 1)2^3 – 1$ has binary representation 0000001111111110111}$

$\text{$2^6((2^{10} – 1)2^3 – 1)$ has binary representation 1111111110111000000}$

$\text{(shifted $6$ bits left because $2^6$ is multiplied)}$

$\text{$N = 523712 = 1111111110111000000$}$

$\textbf{Answer: (E)}$

Answer 3

total sum= 1+2+3+…….+1023 = 523776

now N = 523776- (2+3+11+17+31) = 523712

hence converting N to decimals till the last 8 least significant bits= 11000000. Hence option E is the answer