「dポイント」が最大20倍になるお得な情報

自分で考えた数学の問題が解けません

それぞれの数列akが以下で与えられるとする
a1=0,1,0,1,...
a2=0,0,1,1,0,0,1,1,...
a3=0,0,0,1,1,1,0,0,0,1,1,1...
ak=[k個の0][k個の1][k個の0][k個の1]...


この時、akₙをakの第n項として
a1ₙ=a2ₙ=a3ₙ=...=a100ₙ=0 (n≧2)
を満たす最小のn
また 
a1ₘ=a2ₘ=a3ₘ=...=a100ₘ=1
を満たす最小のmを求めてください

質問者からの補足コメント

  • No3さん
    ご解答ありがとうございます。しかし手元のC言語環境ではN0が37以上では計算に時間がかかりすぎるためタイムアウトとなってしまうようです。ちなみにN0=36の時の解が
    m=3084480、n=28627201
    でした
    アルゴリズムを工夫すれば100まで届くかもしれません

      補足日時:2017/10/02 11:11
  • No4さん
    ご回答ありがとうございます
    発想をいただいて少し考えてみました

    まず話を簡単にするためにnの解だけに絞ります。a(1)(n),a(2)(n),a(4)(n),a(8)(n),...a(64)(n)が全て0であるためにはnを64×2で割った余りが1でなければならない。他の数列を見るとa(3)(n),a(6)(n),a(12)(n),..,a(96)(n)が全て0であるためにはn mod (96×2) <=3であればよく余剰の候補は1つではない。
    一般的に、bが公比2の等比数列でbx<=100であるとき、a(bx)が全て0てあるためにはn mod (末項×2)≦初項の値を満たす必要がある
    そこで末項100以下の公比2の等比数列(項が一つのものも含む)を一覧にすると

      補足日時:2017/10/05 10:31
  • 1,2,4,8,16,32,64
    3,6,12,24,48,96
    5,10,20,40,80
    7,14,28,56
    9,18,36,72
    11,22,44,88
    13,26,52
    15,30,60
    17,34,68
    19,38,76
    21,42,84
    23,46,92
    25,50
    27,54
    29,58
    31,62
    33,66
    35,70
    37,74
    39,78
    41,82
    43,86
    45,90
    47,94
    49,98
    53
    55
    57
    59
    61
    63
    65
    67
    69
    71
    73
    75
    77
    79
    81
    83
    85
    87
    89
    91
    93
    95
    97
    99
    ここから全ての末項の2倍の最小公倍数139440750459424954329067617870624607113600
    から解の一つ

      補足日時:2017/10/05 10:34
  • m=139440750459424954329067617870624607113600
    n=139440750459424954329067617870624607113601
    が得られました
    しかし、最小の解を求めるには余剰の候補が膨大な数になるため、別の手段が必要なようです

      補足日時:2017/10/05 10:35
  • No.5さん
    残念ながらご回答の2714762985719493114806401はa(k)においてk=53,61,79,83,89の時に条件を満たしていないので間違っています。しかしせっかくプログラムを組んでいただいたので、参考のために良ければそのコードを教えていただけないでしょうか

      補足日時:2017/10/06 19:15

A 回答 (8件)

ん, 確かにプログラムが間違ってた. というわけで直してみたところ


全て0: 2623766616792921601
全て1: 10710754295851209600
となった. 想像したよりずっと小さい値だ.

プログラムは Perl で書いてこんな感じ. 現状「全部 0」を探すようになってるけど, 行末に # がある行を (先頭に # を入れて) コメントアウトし, その下の (# ではじまっている行の) # を外すと「全部 1」を探すようになる.

#!/usr/bin/perl

use strict;
use feature 'say';
use Math::BigInt;

sub gcd {
my ($a, $b) = @_;
while ($b != 0) {
my $r = $a % $b;
$a = $b;
$b = $r;
}

$a;
}

my $Limit = 100;
my $last = 100;
my $period = Math::BigInt->new(1); $period *= 2 while $period <= $Limit;
my @candidates = (Math::BigInt->new(0)); #
# my @candidates = ($period-1);
my $candidates = @candidates;

my @bases = (3, 9, 27, 81, 5, 15, 25, 45, 75, 7, 21, 35, 49, 63, 11, 33, 55, 77, 99, 13, 39, 65, 91, 17, 51, 85, 19, 57, 95, 23, 69, 29, 87, 31, 93, 37, 41, 43, 47);

my @largePrimes = (53, 59, 61, 67, 71, 73, 79, 83, 89, 97);

for my $i (@bases) {
my $powi = $i;
$powi *= 2 while $powi <= $Limit;

@candidates = map { [ $_, Math::BigInt::numify($_ % $powi)] } @candidates;
my $modPeriod = Math::BigInt::numify($period % $powi);

my $iter = Math::BigInt::numify($i/gcd($period, $i));
say "i = $i, iter = $iter";

my @newCandidates;
my $newCandidates = 0;
for my $k (0 .. ($iter-1)) {
say "k = $k";

my $offset = $k * $period;
for my $c (@candidates) {
if (($c->[1] + $k * $modPeriod) % $powi < $i) { #
# if (($c->[1] + $k * $modPeriod + $i) % $powi < $i) {
++$newCandidates;
push @newCandidates, $c->[0] + $offset;
}
}
}

@candidates = @newCandidates;
$candidates = $newCandidates;
$period *= $iter;
say "i = $i, period = $period, #candidates = $candidates";
}

shift @candidates; push @candidates, $period; #
#
my @doubleLargePrimes = map { 2*$_ } @largePrimes;
my @modPeriods = map { Math::BigInt::numify($period % $_) } @doubleLargePrimes;
my @modCandidates;
for my $candidate (@candidates) {
push @modCandidates, [map { Math::BigInt::numify($candidate % $_) } @doubleLargePrimes];
}

outer: for (my $k = Math::BigInt->new(0); 1; ++$k) {
my $offset = $k * $period;
my @modK = map { Math::BigInt::numify($k % $_) } @doubleLargePrimes;
for my $j (0 .. ($candidates-1)) {
say "Checking " . ($candidates[$j] + $offset);
my $good = 1;
for my $p (0 .. $#largePrimes) {
if (($modCandidates[$j][$p] + $modK[$p] * $modPeriods[$p]) % $doubleLargePrimes[$p] >= $largePrimes[$p]) {#
# if (($modCandidates[$j][$p] + $modK[$p] * $modPeriods[$p] + $largePrimes[$p]) % $doubleLargePrimes[$p] >= $largePrimes[$p]) {
say "NG at $largePrimes[$p]";
$good = 0;
last;
}
}
if ($good) {
say "Found answer, " . ($candidates[$j] + $offset + 1);
last outer;
}
}
}
    • good
    • 0
この回答へのお礼

ありがとうございました。最小かどうかはこちらでは証明できませんがこれで正解のようです

お礼日時:2017/10/08 09:15

回答になっていなくてすいません。



>a(1)(n),a(2)(n),a(4)(n),a(8)(n),...a(64)(n)が全て0であるためにはnを64×2で割った余りが1でなければならない。
そうですね。それ以外ではどれかが1になるので、必要十分条件になるようです。

以下の定理を証明すれば、効率的なアルゴリズムの発見につながる気がします。

定理1
ak (k = 1,2,4,...,2^n) に対し、
∀k, ak(x)=0 → x=iK+1 (i=0,1,...)
∀k, ak(x)=1 → x=iK (i=1,2,...)
ただしK = 2^(n+1)

系1
ak (k = s,2s,4s,...,s*2^n)に対し、
∀k, ak(x)=0 → x=iK+j (i=0,1,... , j=1,2,...,s)
∀k, ak(x)=1 → x=iK+j (i=1,2,... , j=0,-1,-2,...,1-s)
ただしK = s * 2^(n+1)
    • good
    • 0

回答になっていなくてすいません。



>全ての末項の2倍の最小公倍数から解の一つが得られました
ややこしいことしていますが、
「全ての末項の2倍の最小公倍数」は、単純に「100以下の数の最小公倍数の2倍」ということでは?

本問題(数列akの全て)は、周期性がある。
周期をKとおくと、K=100以下の数の最小公倍数の2倍である。
全てのakのOR値を取ったbk、AND値の数列ckを考える
bk(1)=0, ck(K)=1は自明な解である

で、本質問は、自明でない解を求めたいということではないのですか?
    • good
    • 0

あ, プログラムが止まった.



確かめてはいないけどプログラムが正しければ「すべて 0」となるのは, 1 の次は
2714762985719493114806401
らしい.
    • good
    • 0

ちょっと考えたけど面倒だなぁ....



まずもともとの数列に規則性があるのでそれを使うと効率があがります. 例えば a(2^k) を並べるとちょうど 2進数で 1ずつ増やしていくことに相当するので, n を 128 で割った余りは 1 でなければなりません. 同じことは a3, a6, a12, ... でもでき, これによって n の候補をさらに絞っていくことができます.

ただし, これを本当にやるのはかなり大変です. 単純にプログラムを組むと候補を全て覚えておかねばならず, メモリを食い潰すことになると思います. 全部覚えるのをあきらめて再帰で組むとメモリの代わりに時間を食い潰すことになります. あと扱う数値がたぶんとっても大きくなるので, たいていの C の処理系では多倍長演算を使うことになるでしょう.
    • good
    • 0

No2 です


以下のプログラムのN0を100にすれば、n,mが求まります。
n,m < 100! なので、必ず解が求まります。
ちなみに、
N0= 3 のとき  4, 9
N0= 5 のとき  16, 25
N0=10 のとき  336, 145
N0=20 のとき  2880, 131041
N0=30 のとき 211680, 776161
でした。
ーーーー
#include <stdio.h>
#define N0 100

int a(int k,int n)
{
int i;
i = (n+k-1)/k;
return (1 - i % 2);
}

int b(int n)
{
int i;
for(i=1; i<=N0; i++) {
if(a(i,n) == 0) return 0;
}
return 1;
}

int c(int n)
{
int i;
for(i=1; i<=N0; i++) {
if(a(i,n) == 1) return 1;
}
return 0;
}

int main(void)
{
int n;

n=2;
while(b(n)==0) n++;
printf("b(%d)= 1\n",n);

n=2;
while(c(n)==1) n++;
printf("c(%d)= 0\n",n);
}
    • good
    • 0

有限なので、解はありますね。


Bi(n) = ∧Ai(n)
Ci(n) = ∨Ai(n)
と定義してBi(n)、Ci(n)の表を、コンピュータプログラムで計算して求めれば、一発で答が見つかりますよ。

なお
∧ は 1∧1= 1, 1∧0 = 0∧1 = 0∧0 = 0
∨ は 1∨1= 1∨0= 0∨1=1, 0∨0=0
という演算子です。
    • good
    • 0

「自分で考えた数学の問題」って、


答がある事を確認しての出題ですか。

n,m 共に「解ナシ」だと思います。
n については、第1項は、全て 0 ですが、(k+1)項は必ず 1 の筈。
m については、 k 項までは、必ず 0 が続く筈。

k の値(又は範囲)を特定すれば、答えが存在するでしょう。
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!


人気Q&Aランキング