Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It only takes a minute to sign up.
Sign up to join this community
Given a digit x (between 0 to 9, inclusive) and a number n, calculate the sum of the first n terms of the following sequence:
\$x,10x+x,100x+10x+x,\dots\$
For example, if x is 6 and n is 2, then the result will be 6+66 meaning 72.
There can be trailing whitespace in the output but not leading whitespace.
lambda x,n:(10**-~n/9-n)/9*x
-6 thanks to @Bubbler and @tsh
Aha the first answer I have used some math
How?
Let's call \$n^{th}\$ term as \$y\$
$$ S_n=x+(10x+x)+(100x+10x+x)+.....+y\\= x+(11x)+(111x)+.....+y\\=\frac{x}{9}(9+99+999+.....+y)\\=\frac{x}{9}((10-1)+(100-1)+(1000-1)+.....+y)\\=\frac{x}{9}((10+100+1000+.....+y)-(1+1+1+.....+1))\\=\frac{x}{9}((10^1+10^2+10^3+...+y)-n)\\=\frac{x}{9}(\frac{10(10^n-1)}{10 - 1}-n)\\=\frac{x}{9}(\frac{10(10^n-1)-9n}{9})\\=\frac{x(10(10^n-1)-9n)}{81} $$
And we get our magic formula!
(10**-~n/9-n)/9*x is correct
\$\endgroup\$
(10**-~n/9-n)/9*x
\$\endgroup\$
RḌ×
RḌ× Dyadic link; left arg = n, right arg = x
R [1..n]
Ḍ Undecimal, which is the same as 1 + 11 + ... + (n copies of 1)
× Multiply x
These are the "backports" of the same algorithm into J and APL:
*10#.1+i.
1+ is needed because J does not have 1-based range built-in.
10⊥×∘⍳
-1 byte thanks to @ovs
Uses a slightly different algorithm for golfing purposes: multiply x to 1..n, and then evaluate as base 10. This version of the algorithm works in Jelly too: R×Ḍ. Try it online!
t=>g=n=>n&&t*n+10*g(n-1)
$$ f(n,x)=\sum_{i=1}^n 10^{n-i}\cdot i\cdot x $$ $$ f(n,x)=nx+10\cdot f(n-1,x) \\ f(0,x)=0 $$
For example, we have:
\$f(6,3)\\ =6+66+666\\ =6+(60+6)+(600+60+6)\\ =600×1+60×2+6×3\\ =((6×1)×10+6×2)×10+6×3\\ =10\cdot f(6,2)+6×3\$
=SUM(--REPT(A1,SEQUENCE(A2)))
x is input in A1 and n is input in A2. The formula goes anywhere else in the same sheet.
SEQUENCE(A2) creates an array of all the values from 1 to n.
REPT(A1,~) creates an array of strings of x repeated an increasing number of times based on the array created from the previous step.
--REPT(~) turns those strings into numbers.
SUM(~) adds up those numbers.
R, I*
Thanks to @AaronMiller for -1
-rsƛ⁰ẋ
;)
ƛ⁰ẋ
ƛ # For each number n in the range [1, N]:
⁰ẋ # return x repeated n times (`-r` makes elements take arguments in reverse order)
# The `-s` flag sums the top of the stack before outputting
s flagɾ?vẋ
ɾ?vẋ∑
1#.".\@$
Assuming I can take the digit as a string...
Taking 3 f '6' as an example:
$ - Duplicate:
'666'
".\ Evaluate each prefix:
6 66 666
1#. Sum
738
-2 bytes thanks to Giuseppe
@(x,n)(1:n)*.1.^(1-n:0)'*x
Try it online!
Anonymous function.
How it works
First of all, sum $$x + (10x + x) + (100x + 10x + x) + ... + (10^{n-1}x + 10^{n-2}x + ... 10x + x)$$
can be transformed to:
$$ n\cdot x + 10(n-1)\cdot x + 100(n-2) \cdot x + ... +10^{n-2} \cdot 2 x + 10^{n-1} x $$
which is:
$$ x \cdot \sum_{i=0}^{n-1}(n-i) 10^i =
x \cdot \sum_{i=0}^{n-1}(n-i)\cdot{0.1^{-i}}$$
Having that established:
1:n is vector containing elements 1-n:0 are just indexes of sum above but reversed and negates (so .1.^(1-n:0) is then vector containing elements To get the sum straightforward we would multiply elements of vectors element by element and then sum them like so (whitespace added for readability):
sum( (1:n) .* (.1.^(1-n:0)) )
However, knowing how matrix multiplication works we can just transpose second vector and by multiplying the matrices:
(1:n) * (.1.^(1-n:0))'
we will get exactly the same result. And at the end we just multiply everything by x.
param($x,$n)iex "$(1..$n|%{"+";"$x"*$_})"
iex "$(...)" # Run as a command the result of the list below, joined using spaces
1..$n|%{"+";"$x"*$_} # From 1 to n, build a list containing +,x,+,xx,+,xxx,+,xxxx,...
function(d,n)sum(10^(1:n)-1)*d/9
$$ x + (10x + x) + (100x + 10x + x) + \ldots = \\ x + 11x + 111x + \ldots = \\ (9x + 99x + 999x + \ldots)/9 = \\ (9+99+999+\ldots)*x/9 = \\ ((10-1)+(100-1)+(1000-1)+\ldots)*x/9 = \\ \big[\sum_{i=1}^n(10^i-1)\big]*x/9 $$
-2 bytes thanks to @Giuseppe
Using @Wasif's formula:
function(d,n)d*(10*(10^n-1)/9-n)/9
Straightforward approach with strings:
function(d,n)sum(strtoi(strrep(d,1:n)))
-4 bytes thanks to @Giuseppe
ẋḌƤS
ẋ repeat `x` `n` times
Ƥ for each prefix
Ḍ convert it from digits to a decimal number
S and sum
lambda x,n:(10**n/.9-n)//9*x
Unfortunately I cannot add comments so I'm reposting Wasif's solution with a small tweak so that it works in both python versions. While at it, also correct the math.
$$ S_n=x+(10x+x)+(100x+10x+x)+...+y\\= x+(11x)+(111x)+...+y\\=\frac{x}{9}(9+99+999+...+\frac{9y}{x})\\=\frac{x}{9}((10-1)+(100-1)+(1000-1)+...+(\frac{9y}{x}+1-1))\\=\frac{x}{9}((10+100+1000+...+(\frac{9y}{x}+1))-(1+1+1+...+1))\\=\frac{x}{9}((10^1+10^2+10^3+...+10^n)-n)\\=\frac{x}{9}(\frac{10^{n+1}-10}{9}-n)\\=\frac{x}{9}(\frac{10(10^n-1)-9n}{9})\\=\frac{x(10(10^n-1)-9n)}{81} $$
* *(1 Xx^*+1).sum
Golfed by Jo King from 28 byte solution:
$^a, $^b replaced by whatever-starsXx cross metaoperator responsible for generating 1, 11, 111...{$^a*(^$^b+1).map(1 x*).sum}
Explanation
$^a is x, $^b is n^$^b+1 is shorthand for 0..^$^b+1, equivalent to 1..$^b.map(1 x*) generates 1, 11, 111....sum adds the n-long sequence: 1 for n=1, 12, 123, etc.{[+] ($^b…1)Z*($^a,* *10…*)}
Explanation
Z* zip-multiplies two lists, based on the observation that
1E0 appears n times1E1 appears n-1 times1E2 appears n-2 times, etc.
lambda x,n:sum(int(x*-~i)for i in range(n))
Accepts x as a string and n as an integer. If that's not acceptable, just use lambda x,n:sum(int(`x`*-~i)for i in range(n)) in Python 2 for +2 (+5 with str(x) in Python 3).
{for(;$2--;b+=a)a=a$1}$0=b
I had an alternate algorithm I thought might be interesting, but it the code was longer... So this is pretty much a direct translation of the steps in the challenge description.
{for(;$2--; ) }
Fir every line of input, the code runs the loop the number of times given by the second input parameter, the n value.
a=a$1
The body of the loop appends another copy of the first input parameter to the requested digit, meaning the x value.
b+=a
At the end of each iteration, the accumulator variable b is incremented by the current value of the digits placeholder.
$0=b
Finally, once the processing is done, $0=b overwrites the input line to display the accumulator value.
The only "trick" here is relying on the way AWK will happily treat variables as both strings and integers. Meaning, you can append digits together and still do mathematical operations using the results.
n#x=x*div(10*10^n-9*n)81
Uses Wasif's formula.
0#x=0
n#x=n*x+10*(n-1)#x
A port of tsh's excellent recursive formula.
math.unicode, 44 bytes[ [1,b] [ 10^ 1 - swap 9 / * ] with map Σ ]
Using the first thing that came to mind, $$ f(x,n)=\sum_{i=1}^n \frac{x}{9}(10^{i} - 1) $$
~:x;0\),(;{'1'*~x*+}%
takes as input a string containing n and x, in that order
~:x;0\),(;{'1'*~x*+}%
~ // parse the input string given
:x; // bind the top value to the x variable
0\ // place a zero at the bottom of the stack
),(; // create a list of numbers [1..n]
{ // begin code block
'1'*~ // create and evaluate a string of '1's to get the numbers 1, 11, 111...
x*+ // multiply by x and add to the total (the zero we added)
}% // execute this over every value in the list
// implicitly print the stack
Saved 2 bytes thanks to Olivier Grégoire!!!
t;s;f(x,n){for(s=t=0;n--;)s+=t=t*10+x;n=s;}
t;s;f(x,n){for(s=t=0;n--;)s+=t=t*10+x;n=s;} saves 2 bytes, similarly to my Java answer.
\$\endgroup\$
May 18, 2021 at 15:08
(a,b)=>Enumerable.Range(1,b).Sum(x=>Enumerable.Range(0,x).Sum(y=>a*Math.Pow(10,y)))
(a,b)=>a*(10*(Math.Pow(10,b)-1)-9*b)/81
(a,b)=>b>0?a*b+10*f(a,b-1):0
func[x n][t: s: 0 loop n[t: t + s: s * 10 + x]]
func[x n][t: copy""s: 0 loop n[s: s + to 1 append t x]]
.+(.)
*$1
L$v`.+
*
_
Try it online! Link includes test cases. Takes n as the first input. Note: Struggles for large values of n (5 is just about doable). Explanation:
.+(.)
*$1
Generate n copies of x.
L$v`.+
*
Convert each suffix to unary.
_
Take the sum and convert to decimal.
n takes 33 bytes: Try it online!
\$\endgroup\$
$+YaX\,b
a & b are command-line args (implicit)
aX String-multiply the digit by each number in...
\,b inclusive range from 1 through the number of terms
Y Yank (to enforce desired precedence)
$+ Fold on addition
Autoprint (implicit)
