lowest_contribution's blog

I think I found something intresting please help me prove/disprove this.
By lowest_contribution, history, 14 months ago, In English

A set of tiles are numbered 1-N, In one step you can remove all tiles with a square number,and than rename all the tiles,starting from 1. This is the question,

and what I found is is formula ceil((sqrt(N)-1)*2)

I tried many values still unsuccessfull of proving or disproving anything about this question,

Please Help me prove or disprove this cool formula or trick I would rather say.

  • Vote: I like it
  • +16
  • Vote: I do not like it

Comments Comments (30)
| Write comment?
»
14 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

hmm.. interesting

→ Reply
»
14 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

What does the formula calculate?

→ Reply
»
14 months ago, hide # |
← Rev. 3  
Vote: I like it +1 Vote: I do not like it

lets find all intervals $$$[l_i, r_i]$$$ that for all numbers from i-th interval, we need do $$$i$$$ steps. we know that $$$l_0 r_0 = {0, 0}$$$, now we need to find next segment. its easy to understand that $$$l_{i+1} = r_i + 1$$$ so we need find only $$$r_{i+1}$$$. lets say we have X tiles, we know that we will remove exactly $$$\sqrt{X}$$$ tiles, so $$$r_{i+1} - \sqrt{r_{i+1}} = r_i$$$ here we get a formula that can be solved by the discriminant.
my solution
I wrote the code and got the following segments:
$$$0$$$ from $$$1$$$ to $$$1$$$
$$$1$$$ from $$$2$$$ to $$$2$$$
$$$2$$$ from $$$3$$$ to $$$4$$$
$$$3$$$ from $$$5$$$ to $$$6$$$
$$$4$$$ from $$$7$$$ to $$$9$$$
$$$5$$$ from $$$10$$$ to $$$12$$$
We can see that

$$$r_i = \frac{i + 2}{2} * ((i + 2) - \frac{i + 2}{2}) = \frac{(i + 2)^2}{4}$$$

knowing all the above, I can get the expression that you described

→ Reply
  • »
    »
    14 months ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    during my wrong calculations I got another formula (BUT IT WORKS)

    $$$i = \frac{-4 + \left\lfloor \sqrt{16 + 16 * (N - 1) - 8} \right\rfloor}{2} + 1$$$
    → Reply
  • »
    »
    14 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    cool can you share the code with me?

    → Reply
    • »
      »
      »
      14 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it 
      //```//    YF YUSUF
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
	ll l = 1, r = 1;
	cout<<"0 from 1 to 1\n";
	for(int i=1;i<=10;i++){
		l=r+1;
		ll d = 1 + sqrt(1 + r * 4);
		d = d * d / 4; 
		r = d;
		cout<<i<<" from "<<l<<" to "<<r<<'\n';
	}
	return 0;
}
//```
      → Reply
»
14 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it 
#include <bits/stdc++.h>
using namespace std;

int main() {
    const int N = 1e9;
    vector<int> dp(N + 1);
    dp[1] = 0;
    for(int i = 2; i <= N; i++){
        int removed = sqrt(i);
        dp[i] = dp[i - removed] + 1;
        assert(dp[i] == ceil((sqrtl(i) - 1) * 2));
    }
}

This works on my PC, so I guess proof by AC? I asked chatgpt to prove by induction and I think it's right, but I won't bother reading the proof carefully:

https://chatgpt.com/share/688b4d1c-84f8-8011-b237-2fd33527475b

→ Reply
»
14 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

This is only an approximation;

Assume we start with $$$n$$$.

$$$(\sqrt n - 1)^2 = n - 2\sqrt n + 1 \lt n - \sqrt n$$$ (the numbers left after the first step), so we remove the squares of the numbers $$$1\ldots\sqrt n$$$ and $$$1\ldots\sqrt n - 1$$$ (kind of).

So in two steps, we reach from $$$n = (\sqrt n)^2$$$ to $$$(\sqrt n - 1)^2$$$, then in another two $$$(\sqrt n - 2)^2$$$, etc.

And this gives $$$2\sqrt n$$$ steps.

→ Reply