Numbers k such that the last letter of k is the same as the first letter of k+1: Difference between revisions
Content added Content deleted
(Python example) |
m (→{{header|Python}}: cleanuup unneeded) |
||
| Line 330: | Line 330: | ||
except for numbers > 1000 which are divisible by 1000 """ |
except for numbers > 1000 which are divisible by 1000 """ |
||
groups = [] |
groups = [] |
||
if n < 1: # exception for zero, return array containing zero |
|||
return [n] |
|||
while n > 0: |
while n > 0: |
||
n, r = divmod(n, 1000) |
n, r = divmod(n, 1000) |
||
| Line 344: | Line 342: | ||
def lastletter(n): |
def lastletter(n): |
||
return num2words(n)[-1] if |
return num2words(n)[-1] if n % 1000 == 0 else spelledcache[nonzerogroupings(n)[0]][-1] |
||
else spelledcache[nonzerogroupings(n)[0]][-1] |
|||
def qualifies(n): |
def qualifies(n): |
||
Revision as of 01:41, 1 July 2023
Numbers k such that the last letter of k is the same as the first letter of k+1 is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
- Definition
For the purposes of this task, a qualifying number is a non-negative integer, k, whose last letter is the same as the first letter of k+1 when written in English.
For example, 18 (i.e 'eighteen' in English) is a qualifying number because its last letter 'n' is the same as the first letter of 'nineteen'.
Take the English equivalent of 0 to be 'zero' and not 'nought' or similar words.
For numbers such as 100 or 1000, the equivalent English should be taken as 'one hundred' or 'one thousand' and not 'a hundred' or 'a thousand'.
- Task
1. Find and show here the first 50 qualifying numbers.
2. What are the 1,000th and 10,000th qualifying numbers?
3. For the first 1,000 and 10,000 qualifying numbers, show their breakdown by final digit. This can be shown numerically, graphically or both.
If it is difficult for your language to meet all of these requirements, then just do what you reasonably can.
- Stretch
4. What are the 100,000th and millionth qualifying numbers?
5. For the first 100,000 and million qualifying numbers, show their breakdown by final digit.
- References
- OEIS sequence A363659:Numbers k such that the last letter of k is the same as the first letter of k+1 when written in English.
- GCHQ, The GCHQ Puzzle Book, Penguin, 2016. See Puzzle 31, page 37 (referred to in OEIS link).
ALGOL 68
Brute force but only calculating the first and last characters of the name, not the whole name.
BEGIN # find numbers k where the name of k ends with the start of k + 1 #
[]CHAR unit start = ( "o", "t", "t", "f", "f", "s", "s", "e", "n" );
[]CHAR tens start = ( "t", "t", "t", "f", "f", "s", "s", "e", "n" );
[]CHAR unit end = []CHAR( "y", "e", "o", "e", "r", "e", "x", "n", "t", "e" )[ AT 0 ];
[ 0 : 99 ]CHAR s99; # starting characters for 0..99 #
FOR i TO 99 DO
s99[ i ] := IF i < 10 THEN unit start[ i ]
ELIF i = 10 THEN "t"
ELIF i = 11 THEN "e"
ELIF i < 20 THEN unit start[ i - 10 ]
ELSE tens start[ i OVER 10 ]
FI
OD;
s99[ 0 ] := "z";
[ 0 : 99 ]CHAR e99; # ending characters for 0..99 #
FOR i FROM 1 TO 99 DO e99[ i ] := unit end[ i MOD 10 ] OD;
FOR i FROM 10 TO 19 DO e99[ i ] := "n" OD;
e99[ 0 ] := "o"; e99[ 10 ] := "n"; e99[ 12 ] := "e";
# prints a histogram of data scaled to fit in width #
PROC show histogram = ( []INT data, INT width )VOID:
IF LWB data <= UPB data THEN
INT max value := data[ LWB data ];
FOR i FROM LWB data + 1 TO UPB data DO
IF data[ i ] > max value THEN max value := data[ i ] FI
OD;
FOR i FROM LWB data TO UPB data DO
INT v = ROUND ( ( data[ i ] * width ) / max value );
print( ( whole( i, -2 ), ": ", v * "=", ( ( width - v ) + 1 ) * " " ) );
print( ( " (", whole( data[ i ], 0 ), ")", newline ) )
OD
FI # show histogram # ;
[ 0 : 9 ]INT d count; FOR i FROM LWB d count TO UPB d count DO d count[ i ] := 0 OD;
CHAR prev end := "o"; # zero #
INT next to show := 1 000;
INT count := 0;
print( ( "The first 50 numbers:", newline ) );
FOR n WHILE count < 1 000 000 DO
INT k = n - 1;
INT ddd := n; WHILE ddd >= 1 000 DO ddd OVERAB 1 000 OD;
CHAR curr start = IF ddd < 100
THEN s99[ ddd ]
ELSE unit start[ ddd OVER 100 ]
FI;
IF curr start = prev end THEN
count +:= 1;
d count[ k MOD 10 ] +:= 1;
IF count <= 50 THEN
print( ( " ", whole( k, -4 ) ) );
IF count MOD 10 = 0 THEN print( ( newline ) ) FI
ELIF count = next to show THEN
print( ( newline ) );
print( ( "The ", whole( count, 0 ), "th number is: ", whole( k, 0 ), newline ) );
print( ( "Breakdown by final digit of the numbers:", newline ) );
show histogram( d count, 60 );
next to show *:= 10
FI
FI;
INT n99 = n MOD 100;
prev end := IF n99 > 0
THEN e99[ n99 ]
ELIF n MOD 1 000 000 = 0
THEN "n"
ELSE "d"
FI
OD
END- Output:
The first 50 numbers:
0 18 28 38 79 81 83 85 97 102
122 132 142 152 162 172 182 192 208 228
238 248 258 268 278 288 298 308 328 338
348 358 368 378 388 398 799 801 803 805
809 812 821 823 825 829 831 833 835 839
The 1000th number is: 10988
Breakdown by final digit of the numbers:
0: == (12)
1: ====================== (111)
2: ====================== (110)
3: ====================== (111)
4: == (11)
5: ====================== (111)
6: == (11)
7: ====================== (111)
8: ============================================================ (301)
9: ====================== (111)
The 10000th number is: 106652
Breakdown by final digit of the numbers:
0: === (122)
1: ================================= (1301)
2: ===================== (829)
3: ================================= (1301)
4: === (121)
5: ================================= (1301)
6: === (121)
7: ============================== (1211)
8: ============================================================ (2392)
9: ================================= (1301)
The 100000th number is: 1095542
Breakdown by final digit of the numbers:
0: === (1122)
1: ================================ (11301)
2: ===================================================== (18829)
3: ================================ (11301)
4: === (1121)
5: ================================ (11301)
6: === (1121)
7: =============================== (11211)
8: ============================================================ (21392)
9: ================================ (11301)
The 1000000th number is: 10984428
Breakdown by final digit of the numbers:
0: == (11123)
1: ====================== (111301)
2: ====================== (110230)
3: ====================== (111301)
4: == (11121)
5: ====================== (111301)
6: == (11121)
7: ====================== (111211)
8: ============================================================ (299990)
9: ====================== (111301)
J
Using Number names, we can generate a sample of the desired numbers which (in this example) are smaller than a million:
#sample=: I.({:=1|.!.' '{.)|:({.,{:)@us"0 i.1e6
91401
5 10$sample NB. first fifty
0 18 28 38 79 81 83 85 97 102
122 132 142 152 162 172 182 192 208 228
238 248 258 268 278 288 298 308 328 338
348 358 368 378 388 398 799 801 803 805
809 812 821 823 825 829 831 833 835 839
(],. sample {~ <:) 1e3 1e4 NB. 1000th and 10000th
1000 10988
10000 106652
(~.,.#/.~) /:~10|1e3{.sample NB. counts by final digit (first 1e3 k)
0 12
1 111
2 110
3 111
4 11
5 111
6 11
7 111
8 301
9 111
(~.,.#/.~) /:~10|1e4{.sample NB. counts by final digit (first 1e4 k)
0 122
1 1301
2 829
3 1301
4 121
5 1301
6 121
7 1211
8 2392
9 1301
Julia
using Formatting, SpelledOut, UnicodePlots
spell(n) = spelled_out(n, lang = :en)
qualifies(n) = spell(n)[end] == spell(n + 1)[begin]
function testqualifies()
ncount = 0
lastdigits = UInt8[]
println("First 50 qualifying numbers:")
for n in 0:typemax(Int32)
if qualifies(n)
ncount += 1
push!(lastdigits, n % 10)
if ncount < 51
print(rpad(n, 5), ncount % 10 == 0 ? "\n" : "")
elseif ncount in [10^3, 10^4, 10^5, 10^6]
println("\nThe $(spell(ncount))th number is $(format(n, commas = true)).")
println("Breakdown by last digit of the qualifiers up to this:")
display(histogram(lastdigits, nbins=10))
println()
ncount == 1_000_000 && break
end
end
end
end
testqualifies()
- Output:
First 50 qualifying numbers:
0 18 28 38 79 81 83 85 97 102
122 132 142 152 162 172 182 192 208 228
238 248 258 268 278 288 298 308 328 338
348 358 368 378 388 398 799 801 803 805
809 812 821 823 825 829 831 833 835 839
The one thousandth number is 10,988.
Breakdown by last digit of the qualifiers up to this:
┌ ┐
[ 0.0, 1.0) ┤█▍ 12
[ 1.0, 2.0) ┤████████████▊ 111
[ 2.0, 3.0) ┤████████████▊ 110
[ 3.0, 4.0) ┤████████████▊ 111
[ 4.0, 5.0) ┤█▍ 11
[ 5.0, 6.0) ┤████████████▊ 111
[ 6.0, 7.0) ┤█▍ 11
[ 7.0, 8.0) ┤████████████▊ 111
[ 8.0, 9.0) ┤███████████████████████████████████ 301
[ 9.0, 10.0) ┤████████████▊ 111
└ ┘
Frequency
The ten thousandth number is 106,652.
Breakdown by last digit of the qualifiers up to this:
┌ ┐
[ 0.0, 1.0) ┤█▋ 122
[ 1.0, 2.0) ┤█████████████████▉ 1 301
[ 2.0, 3.0) ┤███████████▌ 829
[ 3.0, 4.0) ┤█████████████████▉ 1 301
[ 4.0, 5.0) ┤█▋ 121
[ 5.0, 6.0) ┤█████████████████▉ 1 301
[ 6.0, 7.0) ┤█▋ 121
[ 7.0, 8.0) ┤████████████████▋ 1 211
[ 8.0, 9.0) ┤█████████████████████████████████ 2 392
[ 9.0, 10.0) ┤█████████████████▉ 1 301
└ ┘
Frequency
The one hundred thousandth number is 1,095,542.
Breakdown by last digit of the qualifiers up to this:
┌ ┐
[ 0.0, 1.0) ┤█▋ 1 122
[ 1.0, 2.0) ┤████████████████▊ 11 301
[ 2.0, 3.0) ┤████████████████████████████▎ 18 829
[ 3.0, 4.0) ┤████████████████▊ 11 301
[ 4.0, 5.0) ┤█▋ 1 121
[ 5.0, 6.0) ┤████████████████▊ 11 301
[ 6.0, 7.0) ┤█▋ 1 121
[ 7.0, 8.0) ┤████████████████▊ 11 211
[ 8.0, 9.0) ┤████████████████████████████████ 21 392
[ 9.0, 10.0) ┤████████████████▊ 11 301
└ ┘
Frequency
The one millionth number is 10,984,428.
Breakdown by last digit of the qualifiers up to this:
┌ ┐
[ 0.0, 1.0) ┤█▎ 11 123
[ 1.0, 2.0) ┤███████████▌ 111 301
[ 2.0, 3.0) ┤███████████▍ 110 230
[ 3.0, 4.0) ┤███████████▌ 111 301
[ 4.0, 5.0) ┤█▎ 11 121
[ 5.0, 6.0) ┤███████████▌ 111 301
[ 6.0, 7.0) ┤█▎ 11 121
[ 7.0, 8.0) ┤███████████▌ 111 211
[ 8.0, 9.0) ┤███████████████████████████████ 299 990
[ 9.0, 10.0) ┤███████████▌ 111 301
└ ┘
Frequency
Python
""" rosettacode.org, wiki task regarding OEIS sequence A363659 """
from collections import Counter
from ascii_graph import Pyasciigraph
from num2words import num2words
spelledcache = [num2words(n) for n in range(1000)]
def nonzerogroupings(n):
""" Return groupings of a thousand if not 0, least significant first. The word
representation of integers is via nonzero groups of three consecutive digits
except for numbers > 1000 which are divisible by 1000 """
groups = []
while n > 0:
n, r = divmod(n, 1000)
if r > 0:
groups.append(r)
return groups
def firstletter(n):
return spelledcache[nonzerogroupings(n)[-1]][0]
def lastletter(n):
return num2words(n)[-1] if n % 1000 == 0 else spelledcache[nonzerogroupings(n)[0]][-1]
def qualifies(n):
return lastletter(n) == firstletter(n + 1)
def testqualifies():
""" Test the generation of OEIS sequence A363659 """
ncount = 0
lastdigits = Counter()
print("First 50 qualifying numbers:")
for num in range(1_000_000_000):
if qualifies(num):
ncount += 1
lastdigits.update([num % 10])
if ncount < 51:
print(f'{num:5}', end='\n' if ncount % 10 == 0 else '')
elif ncount in [10**3, 10**4, 10**5, 10**6]:
print(f'\nThe {num2words(ncount)}th number is {num:,}.')
print('Breakdown by last digit of the qualifiers up to this:')
graph = Pyasciigraph()
for line in graph.graph('Frequencies', sorted(lastdigits.items())):
print(line)
print()
if ncount == 1_000_000:
break
if __name__ == '__main__':
testqualifies()
- Output:
First 50 qualifying numbers:
0 18 28 38 79 81 83 85 97 102
122 132 142 152 162 172 182 192 208 228
238 248 258 268 278 288 298 308 328 338
348 358 368 378 388 398 799 801 803 805
809 812 821 823 825 829 831 833 835 839
The one thousandth number is 10,988.
Breakdown by last digit of the qualifiers up to this:
Frequencies
###############################################################################
██ 12 0
██████████████████████████ 111 1
█████████████████████████ 110 2
██████████████████████████ 111 3
██ 11 4
██████████████████████████ 111 5
██ 11 6
██████████████████████████ 111 7
███████████████████████████████████████████████████████████████████████ 301 8
██████████████████████████ 111 9
The ten thousandth number is 106,652.
Breakdown by last digit of the qualifiers up to this:
Frequencies
###############################################################################
███ 122 0
██████████████████████████████████████ 1301 1
████████████████████████ 829 2
██████████████████████████████████████ 1301 3
███ 121 4
██████████████████████████████████████ 1301 5
███ 121 6
███████████████████████████████████ 1211 7
██████████████████████████████████████████████████████████████████████ 2392 8
██████████████████████████████████████ 1301 9
The one hundred thousandth number is 1,095,542.
Breakdown by last digit of the qualifiers up to this:
Frequencies
###############################################################################
███ 1122 0
████████████████████████████████████ 11301 1
████████████████████████████████████████████████████████████ 18829 2
████████████████████████████████████ 11301 3
███ 1121 4
████████████████████████████████████ 11301 5
███ 1121 6
████████████████████████████████████ 11211 7
█████████████████████████████████████████████████████████████████████ 21392 8
████████████████████████████████████ 11301 9
The one millionth number is 10,984,428.
Breakdown by last digit of the qualifiers up to this:
Frequencies
###############################################################################
██ 11123 0
█████████████████████████ 111301 1
████████████████████████ 110230 2
█████████████████████████ 111301 3
██ 11121 4
█████████████████████████ 111301 5
██ 11121 6
█████████████████████████ 111211 7
████████████████████████████████████████████████████████████████████ 299990 8
█████████████████████████ 111301 9
Phix
with javascript_semantics string s99 = repeat('?',100), // starting char of 0..99 e99 = repeat('?',100) // ending char of 0..99 for n=0 to 99 do string s = ordinal(n,true) s99[n+1] = s[1] e99[n+1] = s[$] end for sequence d_count = repeat(0,10) -- nb 0s in [1] .. 9s in [10] integer this_end = 'o', // zero next_to_show = 1e3, count = 0, n = 0; printf(1,"The first 50 numbers:\n") while count<1e6 do integer next = n+1 while next>=1000 do next = floor(next/1000) end while if next>=100 then next = floor(next/100) end if integer next_start = s99[next+1] if next_start=this_end then d_count[remainder(n,10)+1] += 1 count += 1 if count <= 50 then printf(1," %4d%n",{n,remainder(count,10)=0}) end if if count = next_to_show then printf(1,"\nThe %,dth number is: %,d\n",{count,n}) printf(1,"Breakdown by final digit of the numbers:\n") integer mv = max(d_count) for i,d in d_count do printf(1,"%2d: %s (%d)\n",{i-1,repeat('*',round(d*60/mv)),d}) end for next_to_show *= 10 end if end if n += 1 integer n99 = remainder(n,100) // from table or hundred,thousand -> 'd', million (etc) -> 'n': this_end = iff(n99>0?e99[n99+1]:iff(remainder(n,1e6)=0?'n':'d')) end while
- Output:
The first 50 numbers:
0 18 28 38 79 81 83 85 97 102
122 132 142 152 162 172 182 192 208 228
238 248 258 268 278 288 298 308 328 338
348 358 368 378 388 398 799 801 803 805
809 812 821 823 825 829 831 833 835 839
The 1,000th number is: 10,988
Breakdown by final digit of the numbers:
0: ** (12)
1: ********************** (111)
2: ********************** (110)
3: ********************** (111)
4: ** (11)
5: ********************** (111)
6: ** (11)
7: ********************** (111)
8: ************************************************************ (301)
9: ********************** (111)
The 10,000th number is: 106,652
Breakdown by final digit of the numbers:
0: *** (122)
1: ********************************* (1301)
2: ********************* (829)
3: ********************************* (1301)
4: *** (121)
5: ********************************* (1301)
6: *** (121)
7: ****************************** (1211)
8: ************************************************************ (2392)
9: ********************************* (1301)
The 100,000th number is: 1,095,542
Breakdown by final digit of the numbers:
0: *** (1122)
1: ******************************** (11301)
2: ***************************************************** (18829)
3: ******************************** (11301)
4: *** (1121)
5: ******************************** (11301)
6: *** (1121)
7: ******************************* (11211)
8: ************************************************************ (21392)
9: ******************************** (11301)
The 1,000,000th number is: 10,984,428
Breakdown by final digit of the numbers:
0: ** (11123)
1: ********************** (111301)
2: ********************** (110230)
3: ********************** (111301)
4: ** (11121)
5: ********************** (111301)
6: ** (11121)
7: ********************** (111211)
8: ************************************************************ (299990)
9: ********************** (111301)
Wren
Simple brute force approach.
import "./fmt" for Name, Fmt
import "./math" for Nums
var i = 0
var c = 0
var nums = []
var lastDigs = List.filled(10, 0)
var labels = (0..9).map { |d| d.toString }.toList
var prev = Name.fromNum(0) // "zero"
var limit = 1000
while (limit <= 1e6) {
var next = Name.fromNum(i+1)
if (prev[-1] == next[0]) {
if (c < 50) nums.add(i)
var ld = i % 10
lastDigs[ld] = lastDigs[ld] + 1
c = c + 1
if (c == 50) {
System.print("First 50 numbers:")
Fmt.tprint("$3d ", nums, 10)
System.print()
} else if (c == limit) {
Fmt.print("The $,r number is $,d.\n", c, i)
var title = Fmt.swrite("Breakdown by last digit of first $,d numbers", c)
Nums.barChart(title, 80, labels, lastDigs)
System.print()
limit = limit * 10
}
}
prev = next
i = i + 1
}- Output:
First 50 numbers: 0 18 28 38 79 81 83 85 97 102 122 132 142 152 162 172 182 192 208 228 238 248 258 268 278 288 298 308 328 338 348 358 368 378 388 398 799 801 803 805 809 812 821 823 825 829 831 833 835 839 The 1,000th number is 10,988. Breakdown by last digit of first 1,000 numbers -------------------------------------------------------------------------------- 0 ■■ 12 1 ■■■■■■■■■■■■■■■■■■■■■■■■■■■ 111 2 ■■■■■■■■■■■■■■■■■■■■■■■■■■■ 110 3 ■■■■■■■■■■■■■■■■■■■■■■■■■■■ 111 4 ■■ 11 5 ■■■■■■■■■■■■■■■■■■■■■■■■■■■ 111 6 ■■ 11 7 ■■■■■■■■■■■■■■■■■■■■■■■■■■■ 111 8 ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ 301 9 ■■■■■■■■■■■■■■■■■■■■■■■■■■■ 111 -------------------------------------------------------------------------------- The 10,000th number is 106,652. Breakdown by last digit of first 10,000 numbers -------------------------------------------------------------------------------- 0 ■■■ 122 1 ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ 1301 2 ■■■■■■■■■■■■■■■■■■■■■■■■■ 829 3 ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ 1301 4 ■■■ 121 5 ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ 1301 6 ■■■ 121 7 ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ 1211 8 ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ 2392 9 ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ 1301 -------------------------------------------------------------------------------- The 100,000th number is 1,095,542. Breakdown by last digit of first 100,000 numbers -------------------------------------------------------------------------------- 0 ■■■ 1122 1 ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ 11301 2 ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ 18829 3 ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ 11301 4 ■■■ 1121 5 ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ 11301 6 ■■■ 1121 7 ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ 11211 8 ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ 21392 9 ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ 11301 -------------------------------------------------------------------------------- The 1,000,000th number is 10,984,428. Breakdown by last digit of first 1,000,000 numbers -------------------------------------------------------------------------------- 0 ■■ 11123 1 ■■■■■■■■■■■■■■■■■■■■■■■■■■ 111301 2 ■■■■■■■■■■■■■■■■■■■■■■■■■■ 110230 3 ■■■■■■■■■■■■■■■■■■■■■■■■■■ 111301 4 ■■ 11121 5 ■■■■■■■■■■■■■■■■■■■■■■■■■■ 111301 6 ■■ 11121 7 ■■■■■■■■■■■■■■■■■■■■■■■■■■ 111211 8 ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ 299990 9 ■■■■■■■■■■■■■■■■■■■■■■■■■■ 111301 --------------------------------------------------------------------------------