I think I found a way how to mimic the elementary addition for arbitrary finite groups $G$:

Let $G$ be a finite group, $S \subset G$ a generating set, $|g|:=|g|_S=$ word-length with respect to $S$. Let $\phi(g,h)=|g|+|h|-|gh| \ge 0$ be the "defect-function" of $S$. The set $\mathbb{Z}\times G$ builds a group for the following operation:

$$(a,g) \oplus (b,h) = (a+b+\phi(g,h),gh)$$

On $\mathbb{N}\times G$ is the "norm": $|(a,g)| := |a|+|g|$ additive, which means that $|a \oplus b| = |a|+|b|$. Define the multiplication with $n \in \mathbb{N_0}$ to be:

$$ n \cdot a := a \oplus a \oplus \cdots \oplus a$$

(if $n=0$ then $n \cdot a := (0,1) \in \mathbb{Z} \times G$).

A word $w := w_{n-1} w_{n-2} \cdots w_0$ is mapped to an element of $\mathbb{Z} \times G$ as follows:

$$\zeta(w) := \oplus_{i=0}^{n-1} (m^i \cdot (0,w_i))$$

where $m := \min_{g,h\in G, \phi(g,h) \neq 0} \phi(g,h)$.

We let $|w|:=|\zeta(w)|$ and $w_1 \oplus w_2:=\zeta(w_1)\oplus \zeta(w_2)$

Then we have $|w_1 \oplus w_2| = |w_1|+|w_2|$.

For instance for the Klein four group $\{0,a,b,c=a+b\}$ generated by $S:=\{a,b\}$, we get sorting the words $w$ by their word-length:

$$0,a,b,c,a0,aa,ab,ac,b0,ba,bb,bc,c0,ca,cb,cc,a00,a0a,a0b,a0c$$

corresponding to the following $\mathbb{Z}\times K_4$ elements $\zeta(w)$:

$$(0,0),(0,a),(0,b),(0,c),(2,0),(2,a),(2,b),(2,c),(2,0),(2,a),(2,b),(2,c),(4,0),(4,a),(4,b),(4,c),(4,0),(4,a),(4,b),(4,c)$$

corresponding to the the following "norms" of words $|w| = |\zeta(w)|$:

$$0,1,1,2,2,3,3,4,2,3,3,4,4,5,5,6,4,5,5,6$$

It would be interesting to see what sequence one gets for the smallest non-abelian group $S_3$. If someone likes to write a computer program to compute this, that would be great.

Related questions:
How is this group theoretic construct called?

**Edit**:
Here is some python code for the cyclic groups and an example for $b=3$:

```
def add(a,b,n=2):
x,y = a
c,d = b
return(x+c+(y%n+d%n-(y+d)%n),(y+d)%n)
def sumadd(l,n=2):
x = (0,0)
for y in l:
x = add(x,y,n=n)
return(x)
def norm(a):
return(abs(a[0])+abs(a[1]))
def mult(x,a,n=2):
return(sumadd([a for i in range(x)],n=n))
def zeta(w,n=2):
return sumadd([mult(n**(len(w)-1-i),(0,w[i]),n=n) for i in range(len(w))],n=n)
def digits(n, b):
if n == 0:
return [0]
digits = []
while n:
digits.append(int(n % b))
n //= b
return digits[::-1]
b = 3
for m in range(1,20):
w = digits(m,b)
print(m, norm(zeta(w,n=b)))
(1, 1)
(2, 2)
(3, 3)
(4, 4)
(5, 5)
(6, 6)
(7, 7)
(8, 8)
(9, 9)
(10, 10)
(11, 11)
(12, 12)
(13, 13)
(14, 14)
(15, 15)
(16, 16)
(17, 17)
(18, 18)
(19, 19)
```

**Update**
Here is some Python Code, to do the computations for the Klein Four group:

```
K4_elements = {'0':0,"a":1,"b":2,"c":3}
K4_group_table = [
["0","a","b","c"],
["a","0","c","b"],
["b","c","0","a"],
["c","b","a","0"]
]
K4_lengths = {"0":0,"a":1,"b":1,"c":2}
def K4_add(g,h):
i = K4_elements[g]
j = K4_elements[h]
return(K4_group_table[i][j])
def K4_phi(g,h):
return(K4_lengths[g]+K4_lengths[h]-K4_lengths[K4_add(g,h)])
def add_ZxK4(a,b):
a0,a1=a
b0,b1=b
return((a0+b0+K4_phi(a1,b1),K4_add(a1,b1)))
def sumadd_ZxK4(l):
x = (0,"0")
for y in l:
x = add_ZxK4(x,y)
return(x)
def norm_ZxK4(a):
return(abs(a[0])+K4_lengths[a[1]])
def mult_ZxK4(x,a):
return(sumadd_ZxK4([a for i in range(x)]))
def zeta_ZxK4(w):
m = min([K4_phi(g,h) for g in K4_elements.keys() for h in K4_elements.keys() if K4_phi(g,h)!=0])
return sumadd_ZxK4([mult_ZxK4(m**(len(w)-1-i),(0,w[i])) for i in range(len(w))])
def operate_ZxK4(h,a):
return(add_ZxK4((0,h),a))
from itertools import product
K4 = ['0',"a","b","c"]
words = []
words.extend(list(product(K4,K4,K4)))
for word in words:
print(".".join(word), zeta_ZxK4(word),norm_ZxK4(zeta_ZxK4(word)))
0.0.0 (0, '0') 0
0.0.a (0, 'a') 1
0.0.b (0, 'b') 1
0.0.c (0, 'c') 2
0.a.0 (2, '0') 2
0.a.a (2, 'a') 3
0.a.b (2, 'b') 3
0.a.c (2, 'c') 4
0.b.0 (2, '0') 2
0.b.a (2, 'a') 3
0.b.b (2, 'b') 3
0.b.c (2, 'c') 4
0.c.0 (4, '0') 4
0.c.a (4, 'a') 5
0.c.b (4, 'b') 5
0.c.c (4, 'c') 6
a.0.0 (4, '0') 4
a.0.a (4, 'a') 5
a.0.b (4, 'b') 5
a.0.c (4, 'c') 6
a.a.0 (6, '0') 6
a.a.a (6, 'a') 7
a.a.b (6, 'b') 7
a.a.c (6, 'c') 8
a.b.0 (6, '0') 6
a.b.a (6, 'a') 7
a.b.b (6, 'b') 7
a.b.c (6, 'c') 8
a.c.0 (8, '0') 8
a.c.a (8, 'a') 9
a.c.b (8, 'b') 9
a.c.c (8, 'c') 10
b.0.0 (4, '0') 4
b.0.a (4, 'a') 5
b.0.b (4, 'b') 5
b.0.c (4, 'c') 6
b.a.0 (6, '0') 6
b.a.a (6, 'a') 7
b.a.b (6, 'b') 7
b.a.c (6, 'c') 8
b.b.0 (6, '0') 6
b.b.a (6, 'a') 7
b.b.b (6, 'b') 7
b.b.c (6, 'c') 8
b.c.0 (8, '0') 8
b.c.a (8, 'a') 9
b.c.b (8, 'b') 9
b.c.c (8, 'c') 10
c.0.0 (8, '0') 8
c.0.a (8, 'a') 9
c.0.b (8, 'b') 9
c.0.c (8, 'c') 10
c.a.0 (10, '0') 10
c.a.a (10, 'a') 11
c.a.b (10, 'b') 11
c.a.c (10, 'c') 12
c.b.0 (10, '0') 10
c.b.a (10, 'a') 11
c.b.b (10, 'b') 11
c.b.c (10, 'c') 12
c.c.0 (12, '0') 12
c.c.a (12, 'a') 13
c.c.b (12, 'b') 13
c.c.c (12, 'c') 14
```

Plotting this sequence one recognizes a fractal structure: