Doubt from sequence and series

solved
sequence-series
hard
find-progressive-sequences
pp
#1

For n \ge 1 call a finite sequence (a_1, a_2 \ldots a_n) of positive integers progressive if a_i < a_{i+1} and a_i divides a_{i+1} for all 1 \le i \le n-1. Find the number of progressive sequences such that the sum of the terms in the sequence is equal to 360
Try this
Thanks
Provide detailed solution.

#2

22?

#3

This is a case work approach

a_1+a_2+\cdots +a_n=360

Let a_2=b_1 a_1,\cdots, a_{n}=b_{n-1}a_1 where b_i| b_{i+1}

Then a_1(1+b_1+\cdots b_{n-1})=360

which means we have factorised 360 into two mutually prime factors

These pairs (5,72), (8,45), (9,40)

Now if a_1=5 we need b_1+\cdots+b_{n-1}=71 so we only have b_1=71

so we get 5+ 5\times 71 as one such summation.

with a_1=8 you get (8,32,320), (8,32,64, 256), (8,352), (8,88, 264) and so on.

with a_1=9 it is (9,351), (9,27,54,270), (9,27,81,243), (9,27,108,216), (9,27,324)

with a_1 = 72, (72,288)

a_1=45 we have (45,315)

a_1=40 we have (40,80,240), (40,320)

and of course we have (360)

I think we have 16 here. If I havent missed a case then this should be about it.

1 Like
#4

@Hari_Shankar sir answer is 47

#5

@Hari_Shankar
Sir I would like to know why the numbers cannot be any factors of 360. Why onlt mutually prime factors ...Like a1 can be 1 too.

Taking those I think we can get to the answer

#6

Oh no! I made a mistake there.

Scratch my solution. Gotta try again

1 Like
#7

Okay I found one of the lengthy available solutions there!
I proceeded almost the same as @Hari_Shankar Sir did with the exception that I got the equation in this form
(a_1) (1 + b_1 + b_1b_2 + b_1b_2b_3 + ... ) =360
Now 230 can be written as a product of two numbers in 12 different ways.
But, They are a bit less tedious as they might seem:
First 360 = 1 * 360
a_1 = 1 and the other sum is 360.
Now we can write (1 + b_1 + b_1b_2 + b_1b_2b_3 + ... ) as (1 + b_1(1+b_2(1+b_3....)))
So we now have b_1(1+b_2(1+b_3....))= 359 now 359 being a prime we can't have this possiblity.
Hence a1=1 has only one case i.e. (1,360)
So it gets easy
Similarly proceeding for others we can get the solution!
But it took me almost 15 minutes for this
Might have to think differently

1 Like
#8

If the first term is x, then dividing through by x, we see that we can find the number of progressive sequences whose sum is \frac{360}{x} - 1, and whose first term is not 1. If a(k) denotes the number of progressive sequences whose sum is k and whose first term is not 1, then we can express the answer N as follows:

\begin{align*}N &= a(359) + a(179) + a(119) + a(89) + a(71) + a(59) + a(44) + a(39) \\ &+ a(35) + a(29) + a(23) + a(19) + a(17) + a(14) + a(11) + a(9) \\ &+ a(8) + a(7) + a(5) + a(4) + a(3) + a(2) + a(1) + 1 \end{align*}
The +1 at the end accounts for the sequence whose only term is 360. Fortunately, many of these numbers are prime; we have a(p) = 1 for primes p as the only such sequence is "p" itself. Also, a(1) = 0. So we have

[N = 15 + a(119) + a(44) + a(39) + a(35) + a(14) + a(9) + a(8) + a(4)]
For small k, a(k) is easy to compute: a(4) = 1, a(8) = 2, a(9) = 2. For intermediate k (e.g. k=21 below), a(k) can be computed recursively using previously-computed values of a(\cdot), similar to dynamic programming. Then we have \begin{align*} a(14) &= 1+a(6) = 1+2 = 3\ a(35) &= 1+a(6)+a(4) = 1 + 2 + 1 = 4 \ a(39) &= 2 + a(12) = 2+4 = 6 \ a(44) &= 2 + a(21) + a(10) = 2+4+2=8 \ a(119) &= 1 + a(16) + a(6) = 1 + 3 + 2 = 6 \end{align*} Thus the answer is N = 15+6+8+6+4+3+2+2+1 = \boxed{047}.

1 Like