I have been trying to solve ITRIX12E  R Numbers since very long unfortunately I couldn't solve this. Can anyone please help in solving this problem. asked 13 May, 15:12

Matrix exponentiation should work i think so Let say dp[i][j] denoted the number of Rnumbers of length i ending with j So dp[i][1]=dp[i1][1]+dp[i1][2]+dp[i1][4]+dp[i1][6] .. .. .. dp[i][9]=dp[i1][2]+dp[i1][4]+dp[i1][8] So we have to calculate ,sum(dp[n][j]) for all j We can represent this with matrix :
So we get a matrix ,dp[n]=X*dp[n1] We can expand,dp[n1] similarly So dp[n]=X^(n1)*dp[1] ` answered 13 May, 19:27
@vijju123 do u know how to correct this latex issue,in preview it was showing
(13 May, 20:03)
dp[i][1]=dp[i1][2]+dp[i1][4]+dp[i1][6] ........dp[i][9] Can you please explain why dp[i][9] has been included and dp[i1][1] is missing since 2 is also the prime no.
(17 May, 10:00)
dp[i][9] is not included That ...... means the recurrence relation for dp[i][2],dp[i][3] upto dp[i][9]
(17 May, 10:54)
and why dp[i1][1] is not included in dp[i][1] since here 1+1 will produce 2 which is prime no.
(18 May, 08:31)
dp[2][1]=3 dp[2][2]=4 dp[2][3]=3 dp[2][4]=4 dp[2][5]=3 dp[2][6]=3 dp[2][7]=2 dp[2][8]=3 dp[2][9]=3 If we add them all then it becomes 28, but answer when n=2 is 30
(18 May, 09:10)
Yeah dp[i1][1] should be there,i havemt wrote the exact equations,just written so u could get what i mean. By the wayy for n=30,ans is 29,and in ur above case dp[2][1]=4,so ur ans is also 29 Sum of Rnos of length less than equal to 2 =4+29=33
(18 May, 10:50)
showing 5 of 6
show all
