Substring sums of prime concatenations
Let S(n) be the sum of all contiguous integer-substrings that can be formed from the integer n . The substrings need not be distinct.
For example, S(2024)=2+0+2+4+20+02+24+202+024+2024=2304 .
Let P(n) be the integer formed by concatenating the first n primes together.
For example, P(7)=2357111317 .
Let C(n,k) be the integer formed by concatenating k copies of P(n) together.
For example, C(7,3)=235711131723571113172357111317 .
Evaluate S(C(106 ,1012 )) mod (109 +7) .
计算S(n)的函数

function s(n)
sn=string(n)
le=length(sn)
su=0
for f=1:le
for e=f:le
su+=parse(Int,sn[f:e])
end
end
su
end

上述函数可以简写,但本质没变,考虑到数n可表示为a*10+b,其中a为n/10,b为n%10,可得s(n)=s(a)+f(n),其中f(n)是n%10^x之和。可知,n的各位分别被加了1..len次,即f2(n)再推导得出,s(n)为各位数字*111...11分别*1..len之和,如下:

function s(n)
sn=string(n)
le=length(sn)
sum(parse(Int,sn[f:e])for f=1:le for e=f:le)
end

function f(n)
sn=string(n)
le=length(sn)
sum(n%10^x for x=1:le)
end

function f2(n)
sn=string(n)
le=length(sn)
sum(parse(Int,sn[x])*x*10^(le-x) for x=1:le)
end

function s2(n)
sn=string(n)
le=length(sn)
sum(parse(Int,sn[x])*x*div(10^(le-x+1)-1,9) for x=1:le)
end

用BigInt改写s2函数,可见重复的数字的乘数是预先可以确定的,只要把它们的模计算好,很容易就计算出合计的模。

function s3(n)
sn=string(n)
le=length(sn)
sum(parse(BigInt,sn[x])*x*div(BigInt(10)^(le-x+1)-1,9) for x=1:le)
for x=1:le
println("$(sn[x])*$(x*div(BigInt(10)^(le-x+1)-1,9))")
end
end

julia> s3(123123)
1*111111
2*22222
3*3333
1*444
2*55
3*6

julia> s3(123123123)
1*111111111
2*22222222
3*3333333
1*444444
2*55555
3*6666
1*777
2*88
3*9

构造质数串

p=BitArray(10^6);
function sieve(n)
copy!(p,ones(Bool,n));
p[1]=0
for x=2:floor(Int,sqrt(n))
if p[x]==1
j=x*x
while j<=n
p[j]=0
j+=x
end
end
end
end

w=zeros(Int8,10^7);

function ins(n)
c=1
for i in 2:n
if p[i]==1
s1=string(i)
for x in 1:length(s1)
w[c]=parse(Int8,s1[x])
c+=1
end
end
end
c
end

sieve(10^6)

ins(10^6)

利用111..1=11..1*10+1和余数定理计算重复数字组成的数的模

s=ones(Int64,10^6);
function g(n,m)
for i=2:n
s[i]=(s[i-1]*10+1)%m
end
end

g(10^6,10^9+7)

生成拼接串

function p603(Pn,Cn)
  Ps=primes(Pn*20);
  P=map(string,Ps[1:Pn]);
  w=zeros(Int8,Pn*length(P[Pn]));
  c=1
  for s in P
   for x in 1:length(s)
    w[c]=parse(Int8,s[x])
    c+=1
   end
  end
  wlen=c-1;
  C=zeros(Int8,wlen*Cn)
  for i in 0:Cn-1
   copy!(C,i*wlen+1,w,1,wlen)
  end
 print(C)
end

p603(7,3)

计算S

function p603b(Pn,Cn,m)
  Ps=primes(Pn*20);
  P=map(string,Ps[1:Pn]);
  w=zeros(Int8,Pn*length(P[Pn]));
  c=1
  for s in P
   for x in 1:length(s)
    w[c]=parse(Int8,s[x])
    c+=1
   end
  end
  wlen=c-1;
  su=0
  le=wlen*Cn
  s=ones(Int64,le);
  function g(n,m)
   for i=2:n
    s[i]=(s[i-1]*10+1)%m
   end
  end

  g(le,m);  
  for x=1:le
    su+=(w[(x-1)%wlen+1]*x*s[le-x+1]%m)
  end
  println(su%m)
end

 p603b(100,1000,10^9+7)

用下列函数找到模进入循环的位置

function getg(m)
  s=Int64(1);
  t=1;
  i=Int64(2);
  while(t>0)
    t=(s*10+1)%m
    i+=1;
    s=t;
  end
  i
end

julia> getg(7)
7

julia> getg(17)
17

julia> div(BigInt(10)^(17+16)-1 ,9)%17
1

julia> div(BigInt(10)^(17+16*2)-1 ,9)%17
1

julia> 1111111%7
1

julia> 1111111111111%7
1

从结果可见,m个1组成的数%m==1,然后每增加m+1个1,模发生循环。所以最多只要计算m个长度的g。有的数可以提早进入循环。10^9+7则确实需要这么多次才能进入循环。

julia> getg(10^5+7)
9889

julia> getg(10^9+7)
1000000007

可见,不用保存1...1%m的值,这样可以节省大量存储空间,也解决了无法存储10^9+7个模的问题。

function p603c(Pn,Cn,m::Int64)

function sieve(n)
 p=ones(Int8,n);
 p[1]=0
 for x=2:floor(Int,sqrt(n))
  if p[x]==1
   j=x*x
   while j<=n
    p[j]=0
    j+=x
   end
  end
 end
 [i for i in 1:n if p[i]==1]
end

  Ps=sieve(Pn*20);

  #Ps=primes(Pn*20);
  P=map(string,Ps[1:Pn]);
  w=zeros(Int8,Pn*length(P[Pn]));

  c=Int64(1)
  for s in P
   for x in 1:length(s)
    w[c]=parse(Int8,s[x])
    c+=1
   end
  end
  wlen=c-1;
  su=Int64(0)
  le=wlen*Cn

  st=Int64(1)
  for x=1:le
    su=(su+w[(le+1-x-1)%wlen+1]*(le+1-x)*st%m)%m
    st=(st*10+1)%m
  end
  println(su%m)
end