 # PROBLEM LINK:

Author: Shriram Chandran
Editorialist: Shriram Chandran

Medium

Math, recursion.

# PROBLEM:

Given a number N, find the number of numbers less than or equal to N such that it can be represented as a sum of distinct powers of 3.

There are various solutions to this question.

# EXPLANATION 1:

First, let us make an observation on all 3-regular numbers: they all have only 0s and 1s in their ternary representation. This is because if there is any 2 in the ternary representation, you can not represent it using distinct powers of 3.

Thus, let us find the ternary representation of N, and assume it has d digits. We will now calculate the number of 3-regular numbers having at most d digits and less than N.

Note that all numbers with less than d digits will definitely be smaller than N. Thus for any i digit number, we fix the MSD as 1 and choose one of 2 options for other i-1 digits. So we add to our answer 2^{i-1} for all 1 \leq i \leq d.

For d digit numbers, this does not work. To calculate answer for d digit numbers, we use the following recursion:

• If d=1, the answer is just 1, since N=1 or N=2 and only 1 is 3-regular in these.
• Let d>1. We use the following idea: (i) if a particular digit is 0, we cannot make it 1 or 2 since the number will be greater than N. Thus, we will have to fix 0 when we move to the next digit (ii) if a particular digit is 1, we can fix this as 1 and move to the next digit, or we can fix this digit as 0 and choose any digit for the next positions. (iii) if a particular digit is 2, we can choose 0 or 1 for any digit that comes at or after this digit.
• Do not forget the corner conditions such as last digit or first digit (first digit can not be zero, since we are fixing number of digits and this will lead to repetitions).

Thus, we obtain the recursion f(n,d,i), where n is the number,d is the number of digits and i is the current digit.

# ALTERNATIVE SOLUTION:

Binary search the k^{th} 3-regular number and check how it compares to N. We know that 1 \leq k \leq N.

# ALTERNATIVE SOLUTION 2:

You can run a DP based on the recursion.

# SOLUTION:

Setter's Solution based on recursion
#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll calc(string s,int i)
{
if(s.size()==1)
return 1;
else if(i==s.size()-1)
{
if(s[i]=='0')
return 1;
else return 2;
}
else if(i==0)
{
if(s[i]=='2')
return pow(2,s.size()-1);
else return calc(s,i+1);
}
else
{
if(s[i]=='2')
return pow(2,s.size()-i);
else if(s[i]=='1')
return pow(2,s.size()-i-1)+calc(s,i+1);
else return calc(s,i+1);
}
}

void solve()
{
ll n;
cin>>n;
string s;
ll n1=n;
while(n1)
{
s=(char)(n1%3+48)+s;
n1/=3;
}
ll ans=0;
for(int i=1;i<s.size();i++)
ans+=pow(2,i-1);
ans+=calc(s,0);
cout<<ans<<endl;
}

int main()
{
int t;
cin>>t;
while(t--)
solve();
return 0;
}

1 Like

Thanks for the binary search idea.

There is a simple algorithm to solve the given problem i.e.

Given a number N, find the total numbers less than or equal to N such that it can be represented as a sum of distinct powers of 3.

Pseudo-code:

1. Convert the given (N)_{10} in base-10 to base-3 (N)_{3}.

2. If in base-3 representation, there is a 2 present (can be one or more than one), look for the first-occurrence of 2 from left or MSB.

3. Replace all the numbers after 2 with 1 i.e. 2xxxxx \ldots \rarr 111111 \ldots

4. Now after 3rd-step your number will only contain 1's and 0's. Then find the base-10 representation of the given number by changing the base from 3 to 2. That is the answer.

Let’s take an example to understand what is actually happening:
Lets say the value of N = (96)_{10}, now (96)_{10} in base-3 is (10120)_{3}.
There is only one 2 in the base-3 representation, so we will replace all the numbers after 2 (including 2) by 1, now (10120)_{3} \rarr (10111)_{3}.
Now treat (10111)_{3} as (10111)_{2} and find the base-10 equivalent i.e. (26)_{10} that is the answer.

Proof:
To proof why it works, let’s first understand the sequence which consist of all the numbers that can be expressed as a sum of unique powers of 3.

S(n) = 0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40, 81, 82, \ldots\ldots

Representing every number of the sequence in base-3:

S(n) = (0)_{3}, (1)_{3}, (10)_{3}, (11)_{3}, (100)_{3}, (101)_{3}, (110)_{3}, (111)_{3}, (1000)_{3}, \ldots

If you look closely, every number base-3 representation only consists of 1's and 0's and if you change the base to 2 you will see and then convert that to base-10 it represents its position in the sequence.
So, for example if I want to find the 101^{th} term of the sequence, then I will first find the base-2 representation of (101)_{10} \rarr (1100101)_{2} , and change the base to 3 i.e. (1100101)_{3} and then find the base-10 equivalent that will be (3)^{6} + (3)^{5} + (3)^2 + (3)^1= 729 + 243 + 9 + 3 = 984, that is our 101^{th} term, with same thinking you can find any term of the sequence.

You will discover through experimentation that if we set the first two terms to 0 and 1, the rest of them can be found through the observation that if n is in the sequence, so is 3n and 3n+1.

Now as per the problem, N is natural number that means if you find the base-3 representation for any N which doesn’t belongs to S(n) will have 2 in it, that means that number cannot be represented as a sum of unique powers of 3, so to find the maximum number \leq N that can be represented as sum of unique powers of 3 we find find the first occurrence of 2 from MSB that is the 2 which is at higher positional index and replace everything to one as defined above. After doing that the resultant base-3 representation will be part of S(n).
Now the number of sequence terms below N is the number of integers below that number read in base 2.

Accepted Solution in Python3.

References:

• For more information about S(n) refer to OEIS.

• For the number of terms \leq N refer to the sequence on OEIS.

Thanks for reading.
Peace 3 Likes

I approached initially in the same way. Could not think what to do with ‘2’ coming in notation while in contest. Thanks!!