Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Introduce the function $g(n)$ defined for positive integer arguments $n$ as the count of squares of positive integers among the numbers that can be formed by taking some subsequence of the digits of the binary representation of $n$ and interpreting this subsequence as a binary number. All subsequences contribute.

For example, $5 = (101)_2$ and the subsequences of digits are $$ (1)_2 = 1, (0)_2 = 0, (1)_2 = 1, (10)_2 = 2, (11)_2 = 3, (01)_1 = 1, (101)_2 = 5$$ and this includes the square "one" three times, so $g(5) = 3.$

When $n = 9 = (1001)_2$, we obtain the following subsequences: $$ (1)_2 = 1, (0)_2 = 0, (0)_2 = 0, (1)_2 = 1, (10)_2 = 2, (10)_2 = 2, (11)_2 = 3, (00)_2 = 0, (01)_2 = 1, (01)_2 = 1$$ and $$ (100)_2 = 4, (101)_2 = 5, (101)_2 = 5, (001)_2 = 1, (1001)_2 = 9$$ and this includes seven squares, so $g(9) = 7.$

The behavior of $g(n)$ is highly erratic, ranging from linear for $n=2^k$ to logarithmic for $n=2^k-1,$ which motivates us to ask the following question. What is the first term of the asymptotic expansion of the average order of $g(n)$? I.e. find the asymptotics of $$ \frac{1}{n} \sum_{k=1}^n g(k).$$

It might be useful to establish and prove closed form expressions for special values of $g(n)$, e.g. we have $g(2^k) = 2^{k-1}$ and $g(2^k-1) = k$ as pointed out earlier (prove these). Here are the first few terms of $g(n):$ $$1, 1, 2, 2, 3, 2, 3, 4, 7, 4, 5, 4, 4, 3, 4, 8, 15, 9, 12, 8, 9, 6, 7, 8, 11$$

This problem is not suited to numeric experimentation because $g(n)$ fluctuates so rapidly. For those who want to try anyway here is some C code. (I was going to memoize this the same way I memoized the Maple routine, but never got around to it. This is why the code looks as it does.) C Code for the square indicator sum over binary digit subsequences


#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <readline/readline.h>

unsigned long long isqrt(unsigned long long n)
{
  if(!n) return 0;

  unsigned long long a = 1, b = n, mid;

  do {
    mid = (a+b)/2;
    if(mid*mid>n){
      b = mid;
    }
    else{
      a = mid;
    }
  } while(b-a>1);

  return a;
}

unsigned long long g(unsigned long long n)
{
  int bits[256], len = 0;
  while(n>0){
    bits[len++] = n%2;
    n >>= 1;
  }

  unsigned long long res = 0, ind;
  for(ind=0; ind<(1<<len); ind++){
    unsigned long long varind = ind;
    int subseq[256], srcpos=0, pos=0;
    while(varind>0){
      if(varind%2){
        subseq[pos++] = bits[srcpos];
      }
      srcpos++;
      varind >>= 1;
    }

    unsigned long long val = 0;
    int seqpos = 0;
    while(seqpos<pos){
      val += (1<<seqpos)*subseq[seqpos];
      seqpos++;
    }

    unsigned long long cs = isqrt(val);
    if(val>0 && cs*cs == val){
      res++;
    }
  }

  return res;
}

unsigned long long gavg(unsigned long long max)
{
  unsigned long long res = 0, n;

  for(n=1; n<=max; n++){
    res += g(n);
  }

  return res;
}

int main(int argc, char *argv)
{
  unsigned long long max;
  char *line;

  while((line = readline("> ")) != NULL){
    if(sscanf(line, "%llu", &max)==1){
      unsigned long gsum = gavg(max);

      long double asympt = (long double)gsum;
      asympt = asympt/(long double)max;

      printf("%llu %lle\n", gsum, asympt);
    }
    free(line);
  }

  exit(0);
}

This is the Maple code, which is noticeably slower.Maple Code for the square indicator sum


g :=
proc(n)
        option remember;
        local dlist, ind, flind, sseq, len, sel, val, r, res;

        dlist := convert(n, base, 2);
        len := nops(dlist);

        res := 0;
        for ind from 0 to 2^len-1 do
            sel := convert(ind, base, 2);

            sseq := [];
            for flind to nops(sel) do
                if sel[flind] = 1 then
                   sseq := [op(sseq), dlist[flind]];
                fi;
            od;

            val := add(sseq[k]*2^(k-1), k=1..nops(sseq));

            r := floor(sqrt(val));
            if val>0 and r*r = val then
               res := res+1;
            fi;
        od;

        res;
end;

avg := n -> add(g(k), k=1..n);
share|improve this question
    
Have you checked the oeis? –  Gerry Myerson Dec 8 '12 at 5:47
    
Yes I checked the OEIS for $g(n)$ and several non-trivial subsequences, with no luck yet. Back in a couple of hours. –  Marko Riedel Dec 8 '12 at 5:55
    
why have you posted a picture of source code..... –  user51427 Dec 8 '12 at 19:15
1  
To all: I made a mistake in my bounty comment, and now it won't let me fix the comment. Of course $q(n)$ should be such that $\frac{1}{n} \sum_{k=1}^n g(k) \in \theta(q(n))$, the case for $O(q(n))$ is easy. –  Marko Riedel Dec 10 '12 at 18:54
1  
@ErickWong I would prefer seeing a solution and then comment on that so that stackexchange.com won't complain about this turning into a chat. I do have some relevant ideas myself. Publishing yours might enable another reader to help clinch it where the constant is concerned. I suspect if you were to post C code for an efficient computation of $\sum g(n)$ that would really deepen a reader's understanding of the problem and possibly even enable the computation of additional terms in the asymptotic expansion. Thanks! Back tomorrow. –  Marko Riedel Dec 11 '12 at 1:38
show 10 more comments

1 Answer 1

up vote 1 down vote accepted
+200

This is an answer to the (corrected) bounty question, but I would still like to know if there is an asymptotic formula for the average value of $g(k)$ or whether it fluctuates between multiples of $n^b$.

Let $n = 2^m$ be a power of two, and let $F(n)$ be the number of squares found as subsequences of all binary strings of length $m$, and let $G(n)$ be the exact value of $\sum_{k=0}^{n-1} g(k)$. (It is convenient to start counting at $0$ rather than $1$ but it does not affect the asymptotics.)

It is certainly not true that $F(n) = G(n)$, but it is a useful approximation in two ways. On one hand, $F(n) \ge G(n)$, because every binary string of length $m$ corresponds to some integer in $[0,2^m-1]$ but it has strictly more subsequences because of zero-padding. On the other hand, $F(n) \le \sum_{k=n}^{2n-1} g(k) = G(2n) - G(n)$, because adding a leading $1$ to each binary string of length $m$ yields a legitimate binary integer in $[2^m,2^{m+1}-1]$.

The benefit of this simplified model is that it is very easy to estimate $F(n)$. For each length $1 \le \ell \le m$, there are $m\choose\ell$ subsequences of length $\ell$ within any $m$-bit string. For each choice there will be about $\sqrt{2^\ell}$ (more precisely, $\lfloor \sqrt{2^\ell-1}\rfloor+1$) ways to choose a perfect square to fill in that subsequence. Then there are $2^{m-\ell}$ ways to fill in the remaining bits. Therefore

$$F(n) \approx \sum_{\ell=1}^m {m\choose\ell} (\sqrt{2})^{\ell} 2^{m-\ell} = (\sqrt{2}+2)^m - 2^m,$$ by the binomial formula. Thus $F(n) \sim n^c$ where $c = \log_2(2+\sqrt{2})$, and $\tfrac1n F(n) \sim n^b$ where $b = c-1 = 0.77155\ldots$.

Recall that $G(n) \le F(n) \le G(2n)-G(n)$. Since $F(n) \sim n^c$, the left inequality easily gives $G(n) = O(n^c)$, while the right inequality yields $G(n) \ge G(n)-G(n/2) \ge F(n/2) = \Omega(n^c)$. Therefore $G(n) = \Theta(n^c)$ when $n$ is a power of $2$, and since it is monotonically increasing, this growth rate can be seen to extend to all $n$. The desired function $q(n)$ is thus $n^b$.

share|improve this answer
    
I have studied this response in detail and it appears to be sound, so I will likely award it the bounty. Could you clarify two more things -- when you say "it has more subsequences because of zero padding" do you mean that the squares being counted by $F(n)$ include subsequences that start with zero padding on the left, none of which would contribute to $g(n)$? For the upper bound you consider integers of $m+1$ bits starting with $2^m$. This time there is no loss due to zero padding because of the $1$ on the left? And subsequences including the leftmost bit make it an upper bound? –  Marko Riedel Dec 13 '12 at 21:05
    
@MarkoRiedel That's exactly right. –  Erick Wong Dec 13 '12 at 21:29
    
I will award the bounty. I do not think that we have an asymptotic expansion, it looks like it keeps on fluctuating around $n^b.$ As I noted in my original post there are some simple identities for $g(n)$ for certain values of $n$, like $n=2^k.$ I wonder if it would be interesting to establish more of these and perhaps gain some insight into the sequence that way. I suspect this can be done algorithmically. –  Marko Riedel Dec 13 '12 at 21:40
1  
Essentially the problem is how to compute $g(n)$ for $n$ odd. There are efficient recurrences when $n = q 2^k$, $q$ odd. Let $g_0(n) = g(n)$ and let $g_1(n)$ be like $g(n)$ except that it counts numbers of the form $2m^2$ instead of squares. Then we have $$g_0(q 2^k) = g_0(q) \sum_{r\ge 0} \binom{k}{2r} + g_1(q) \sum_{r\ge 0} \binom{k}{2r+1} $$ and $$g_1(q 2^k) = g_0(q) \sum_{r\ge 0} \binom{k}{2r+1} + g_1(q) \sum_{r\ge 0} \binom{k}{2r}.$$ As pointed out these are very efficient, but there does not appear anything of the sort for odd values. –  Marko Riedel Dec 14 '12 at 0:17
    
It is worth noting that the above recurrence holds for bases other than two that are not squares. When the base (call it $d$) is a square, like four, the recurrence becomes $$g(q d^k) = g(q) 2^k$$ (with $q$ not a multiple of $d$). It seems there are many interesting properties here that can be investigated. –  Marko Riedel Dec 15 '12 at 14:18
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.