免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[数列] 数列与数论结合,7的倍数

考虑数列$\{a_n\}$,$a_1=1,a_n=a_{n-1}+a_{[\frac{n}{2}]}(n=2,3,\cdots)$.求证:数列$\{a_n\}$中有无穷多项7的倍数.
好像以前见过?
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

本帖最后由 realnumber 于 2019-2-6 09:19 编辑

假设数列{$a_n$}中,7的倍数的项不是无限个,则设最大的是第m项($m\ge 5$),符合$7\mid a_m$
此时$a_{2m+1}=a_{2m}+a_m,a_{2m}=a_{2m-1}+a_m$,
即$a_{2m+1}=a_{2m}=a_{2m-1}=t_0   \mod 7$,其中$t_0$是集合{1,2,3,4,5,6}中的某个整数.
此时用同样办法得到($\mod 7$)
$a_{4m+3}-a_{4m+2}=t_0$
$a_{4m+2}-a_{4m+1}=t_0$
$a_{4m+1}-a_{4m}=t_0$
$a_{4m}-a_{4m-1}=t_0$
$a_{4m-1}-a_{4m-2}=t_0$
$a_{4m-2}-a_{4m-3}=t_0$
而这样连续7个项$a_{4m+3},a_{4m+2},a_{4m+1},a_{4m},a_{4m-1},a_{4m-2},a_{4m-3}$一定有且仅有一个被7整除(余数其实各不相同,即是一个完全剩余系,比如两式相加得$a_{4m+3}-a_{4m+1}=2t_0$说明$a_{4m+3},a_{4m+1}$被7除余数不等.).
1楼证明完。

TOP

本帖最后由 realnumber 于 2019-2-9 11:55 编辑

猜想
1)没有被4整除的项,(程序搜索了$2\times10^8$项,没找到一项)
2)有无限项被11整除(程序搜索了300项,就有好多)。
3)有无限项被2019整除 (程序搜索了下,好多,难度我也不知道)
4)考虑数列$\{a_n\}$,$a_1=1,a_2=1,a_n=a_{n-1}+a_{[\frac{n}{3}]}(n=3,4,5\cdots)$.数列$\{a_n\}$中有无穷多项是正整数p的倍数(搜索了$p\le 2020,n\le 2000000$),很不负责任,表示不会 .
怎么证明?

pascal程序:
var
n,p:longint;
d:array[1..200000000] of longint;
begin
d[1]:=1;
p:=4;
for n:=2 to 200000000 do
   begin
     d[n]:=d[n-1]+d[trunc(n div 2)]  mod p;
     if d[n] mod p=0 then  writeln(n, ', ',n mod p,', ',d[n] mod p);
  end;
end.
猜想1的证明,以下用数学归纳法证明(以下$a_n$都是取$\mod 4$后的)
1)当[$\frac{n}{2}$]=1时,$a_1=1$,依次可以$a_1=1,a_2=2,a_3=3$
当[$\frac{n}{2}$]=2时,$a_2=2$依次可得$a_3=3,a_4=1,a_5=3$
当[$\frac{n}{2}$]=3时,$a_3=3$依次可得$a_5=3,a_6=2,a_7=1$
...........
2)当[$\frac{n}{2}$]=k时,$a_k=s,a_{2k-1}=t$,其中归纳假设$s\in${1,2,3},$t\in${1,3}依次可得$a_{2k-1}=t,a_{2k}=t+s\in A,a_{2k+1}=t+2s\in A$,经穷举,假设成立

.....
猜想1成立.
另,只需修改初值,比如$a_1=2$就会出现无数4的倍数.

TOP

本帖最后由 realnumber 于 2019-2-9 22:14 编辑

猜想2的证明可以继续2楼的思路,以下$a_n$的值都是$\mod11$下的.
假设数列{$a_n$}中,11的倍数的项不是无限个,则设最大的是第m项($m\ge 19$,因为$a_{19}=0$),符合$11\mid a_m$
此时$a_{2m+1}=a_{2m}+a_m,a_{2m}=a_{2m-1}+a_m$,
即$a_{2m+1}=a_{2m}=a_{2m-1}=t $,其中$t$是集合A={1,2,3,4,5,6,7,8,9,10}中的某个整数.
三个数$a_{2m+1},a_{2m},a_{2m-1}$都是$t $
此时用同样办法得到
$a_{4m+3}-a_{4m+2}=t$
$a_{4m+2}-a_{4m+1}=t$
$a_{4m+1}-a_{4m}=t$
$a_{4m}-a_{4m-1}=t$
$a_{4m-1}-a_{4m-2}=t$
$a_{4m-2}-a_{4m-3}=t$
而继续这个操作,并记$a_{4m}=s\in  A$
连续7个项$a_{4m+3},a_{4m+2},a_{4m+1},a_{4m},a_{4m-1},a_{4m-2},a_{4m-3}$依次是
$s+3t,s+2t,s+t,s,s-t,s-2t,s-3t$
再次继续这个,并记$a_{8m}=r\in A$
连续15个项 $a_{8m+7},a_{8m+6},\cdots,a_{8m-7}$依次是
$r+7s+12t,r+6s+9t,r+5s+6t,r+4s+4t,r+3s+2t,r+2s+t,r+s,r,r-s,r-2s+t,r-3s+2t,r-4s+4t,r-5s+6t,r-6s+9t,r-7s+12t$
恩,手工算有些麻烦,设想任意的$r,s,t\in A$上面15个数总是存在11的完全剩余系(程序倒能解决),那么问题就证明了,不行的话继续找接下来31个,63个,127个,.....只是个设想.
这个设想也许不会成功,试了下31+15+7+1=54项,程序如下,
var
a:array[0..10] of longint;
b:array[1..54] of longint;
q,r,s,t,n,m,k:longint;
begin
for q:=1 to 10 do
begin
    for r:=1 to 10 do
    begin
      for s:=1 to 10 do
      begin
       for t:=1 to 10 do
       begin
        for n:=0 to 10 do a[n]:=0;
        b[1]:=t;
        b[2]:=s+3*t;
        b[3]:=s+2*t;
        b[4]:=s+t;
        b[5]:=s;
        b[6]:=s-t;
        b[7]:=s-2*t;
        b[8]:=s-3*t;
        b[9]:=r+7*s+12*t;
        b[10]:=r+6*s+9*t;
        b[11]:=r+5*s+6*t;
        b[12]:=r+4*s+4*t;
        b[13]:=r+3*s+2*t;
        b[14]:=r+2*s+t;
        b[15]:=r+s;
        b[16]:=r;
        b[17]:=r-s;
        b[18]:=r-2*s+t;
        b[19]:=r-3*s+2*t;
        b[20]:=r-4*s+4*t;
        b[21]:=r-5*s+6*t;
        b[22]:=r-6*s+9*t;
        b[23]:=r-7*s+12*t;
        b[24]:=q+15*r+56*s+68*t;
        b[25]:=q+14*r+49*s+56*t;
        b[26]:=q+13*r+42*s+44*t;
        b[27]:=q+12*r+36*s+35*t;
        b[28]:=q+11*r+30*s+26*t;
        b[29]:=q+10*r+25*s+20*r;
        b[30]:=q+9*r+20*s+14*t;
        b[31]:=q+8*r+16*s+10*t;
        b[32]:=q+7*r+12*s+6*t;
        b[33]:=q+6*r+9*s+4*t;
        b[34]:=q+5*r+6*s+2*t;
        b[35]:=q+4*r+4*s+t;
        b[36]:=q+3*r+2*s;
        b[37]:=q+2*r+s;
        b[38]:=q+r;
        b[39]:=q;
        b[40]:=q-15*r+56*s-68*t;
        b[41]:=q-14*r+49*s-56*t;
        b[42]:=q-13*r+42*s-44*t;
        b[43]:=q-12*r+36*s-35*t;
        b[44]:=q-11*r+30*s-26*t;
        b[45]:=q-10*r+25*s-20*r;
        b[46]:=q-9*r+20*s-14*t;
        b[47]:=q-8*r+16*s-10*t;
        b[48]:=q-7*r+12*s-6*t;
        b[49]:=q-6*r+9*s-4*t;
        b[50]:=q-5*r+6*s-2*t;
        b[51]:=q-4*r+4*s-t;
        b[52]:=q-3*r+2*s;
        b[53]:=q-2*r+s;
        b[54]:=q-r;
        for n:=1 to 54 do b[n]:=(b[n]+9900) mod 11;
        for n:=1 to 54 do a[b[n]]:=a[b[n]]+1;
        if a[0]=0 then writeln(q,' ',r,' ',s,' ',t);
      end;
    end;
  end;
end;
end.
结果如下
1 5 10 9
1 6 10 2
2 1 9 4
2 10 9 7
3 4 8 5
3 7 8 6
4 2 7 8
4 9 7 3
5 3 6 1
5 8 6 10
6 3 5 1
6 8 5 10
7 2 4 8
7 9 4 3
8 4 3 5
8 7 3 6
9 1 2 4
9 10 2 7
10 5 1 9
10 6 1 2,说明还有这么些情景,没有11的倍数.也许接下来+63个就可以了.
程序略修改下,改成9的倍数猜想,通过.也就是说证明了猜想:数列中有无限项被9整除.
接下来要考虑的是不用写出这么多项,把程序写得漂亮点,这样就可以用来证明11,2019什么的,至于猜想4,这个办法不行吧.
程序修改如下(希望没编错吧,要处理2019这个办法不晓得可不可以?),添了63项,这下,对任意$p,q,r,s,t\in A$,总是存在11的倍数.
var
a:array[-10..10] of longint;
b,c:array[1..119] of longint;
p,q,r,s,t,n,m:longint;
begin
  for p:=1 to 10 do
  begin
    a[0]:=0;
    b[1]:=p; b[2]:=p;b[3]:=p;
    for q:=1 to 10 do
    begin
      b[4]:=q;
      for m:=1 to 6 do
      begin
        b[4+m]:=(b[4+m-1]+b[(m+1) div 2]) mod 11;
        a[b[4+m]]:=a[b[4+m]]+1;
      end;
      if a[0]<>0 then continue;
      for r:=1 to 10 do
      begin
        b[11]:=r;
        for m:=1 to 14 do
        begin
          b[11+m]:=(b[10+m]+b[(m+7)   div 2])mod 11;
          a[b[11+m]]:=a[b[11+m]]+1;
        end;
        if a[0]<>0 then continue;
        for s:=1 to 10 do
        begin
          b[26]:=s;
          for m:=1 to 30 do
          begin
            b[26+m]:=(b[25+m]+b[(m+21)div 2])mod 11;
            a[b[26+m]]:=a[b[26+m]]+1;
          end;
          if a[0]<>0 then continue;
          for t:=1 to 10 do
          begin
            b[57]:=t;
            for m:=1 to 62 do
            begin
              b[57+m]:=(b[56+m]+b[(m+51)div 2])mod 11;
              a[b[57+m]]:=a[b[57+m]]+1;
            end;
            if a[0]=0 then writeln(p,' ',q,' ',' ',r,' ',s,' ',t);
          end;
        end;
      end;
    end;
  end;
end.

TOP

本帖最后由 realnumber 于 2019-2-9 22:05 编辑

var
a:array[0..2018] of boolean;
b:array[1..50000] of longint;
p,q,r,s,t,u,v,w,x,y,z,c,d,m:longint;
begin
  for p:=1 to 2018 do
  begin
    for m:=0 to 2018 do a[m]:=false;
    b[1]:=p; b[2]:=p;b[3]:=p;
    for q:=1 to 2018 do
    begin
      b[4]:=q;
      for m:=1 to 6 do
      begin
        b[4+m]:=(b[4+m-1]+b[(m+1) div 2]) mod 2019;
        a[b[4+m]]:=true;
      end;
      if a[0] then continue;
      for r:=1 to 2018 do
      begin
        b[11]:=r;
        for m:=1 to 14 do
        begin
          b[11+m]:=(b[10+m]+b[(m+7)   div 2])mod 2019;
          a[b[11+m]]:=true;
        end;
        if a[0] then continue;
        for s:=1 to 2018 do
        begin
          b[26]:=s;
          for m:=1 to 30 do
          begin
            b[26+m]:=(b[25+m]+b[(m+21)div 2])mod 2019;
            a[b[26+m]]:=true;
          end;
          if a[0] then continue;
          for t:=1 to 2018 do
          begin
            b[57]:=t;
            for m:=1 to 62 do
            begin
              b[57+m]:=(b[56+m]+b[(m+51)div 2])mod 2019;
              a[b[57+m]]:=true;
            end;
            if a[0] then continue;
            for u:=1 to 2018 do
            begin
              b[120]:=u;
              for m:=1 to 126 do
              begin
                b[120+m]:=(b[119+m]+b[(m+113)div 2])mod 2019;
                a[b[120+m]]:=true;
              end;
              if a[0] then continue;
              for v:=1 to 2018 do
              begin
                b[247]:=v;
                for m:=1 to 254 do
                begin
                  b[247+m]:=(b[246+m]+b[(m+239)div 2])mod 2019;
                  a[b[247+m]]:=true;
                end;
                if a[0] then continue;
                for w:=1 to 2018 do
                begin
                  b[502]:=w;
                  for m:=1 to 510 do
                  begin
                    b[502+m]:=(b[501+m]+b[(m+493)div 2])mod 2019;
                    a[b[502+m]]:=true;
                  end;
                  if a[0] then continue;
                  for x:=1 to 2018 do
                  begin
                    b[1013]:=x;
                    for m:=1 to 1022 do
                    begin
                      b[1013+m]:=(b[1012+m]+b[(m+1003)div 2])mod 2019;
                      a[b[1013+m]]:=true;
                    end;
                    if a[0] then continue;
                    for y:=1 to 2018 do
                    begin
                      b[2036]:=y;
                      for m:=1 to 2046 do
                      begin
                        b[2036+m]:=(b[2035+m]+b[(m+2025)div 2])mod 2019;
                        a[b[2036+m]]:=true;
                      end;
                      if a[0] then continue;
                      for z:=1 to 2018 do
                      begin
                        b[4083]:=z;
                        for m:=1 to 4094 do
                        begin
                          b[4083+m]:=(b[4082+m]+b[(m+4071)div 2])mod 2019;
                          a[b[4083+m]]:=true;
                        end;
                        if a[0] then continue;
                        for c:=1 to 2018 do
                        begin
                          b[8178]:=c;
                          for m:=1 to 8190 do
                          begin
                            b[8178+m]:=(b[8177+m]+b[(m+8165)div 2])mod 2019;
                            a[b[8178+m]]:=true;
                          end;
                          if a[0] then continue;
                          for d:=1 to 2018 do
                          begin
                            b[16369]:=d;
                            for m:=1 to 16382 do
                            begin
                              b[16369+m]:=(b[16368+m]+b[(m+16355)div 2])mod 2019;
                              a[b[16369+m]]:=true;
                            end;
                            if not(a[0]) then writeln(p,' ',q,' ',' ',r,' ',s,' ',t,' ',u,'  ',v,' ',w,' ',x,' ',y,' ',z,' ',c,' ',d);
                          end;
                        end;
                      end;
                    end;
                  end;
                end;
              end;
            end;
          end;
        end;
      end;
    end;
  end;
end.
运行了5,6分钟侥幸通过,证明了2019的倍数也是无限项.猜想3也成立.这样就只有猜想4了 .

TOP

返回列表 回复 发帖