Numbers with equal rises and falls: Difference between revisions
m →{{header|Factor}}: lnth is a thing |
m draft to task |
||
Line 1: | Line 1: | ||
{{draft task}} |
|||
When a number is written in base 10, adjacent digits may "rise" or "fall" as the number is read (usually from left to right). |
When a number is written in base 10, adjacent digits may "rise" or "fall" as the number is read (usually from left to right). |
||
Revision as of 17:41, 10 August 2021
When a number is written in base 10, adjacent digits may "rise" or "fall" as the number is read (usually from left to right).
- Definition
Given the decimal digits of the number are written as a series d:
- A rise is an index i such that d(i) < d(i+1)
- A fall is an index i such that d(i) > d(i+1)
- Examples
-
- The number 726,169 has 3 rises and 2 falls, so it isn't in the sequence.
- The number 83,548 has 2 rises and 2 falls, so it is in the sequence.
- Task
-
- Print the first 200 numbers in the sequence
- Show that the 10 millionth (10,000,000th) number in the sequence is 41,909,002
- See also
- OEIS Sequence A296712 describes numbers whose digit sequence in base 10 have equal "rises" and "falls".
- Related tasks
11l
<lang 11l>F riseEqFall(=num)
‘Check whether a number belongs to sequence A296712.’ V height = 0 V d1 = num % 10 num I/= 10 L num != 0 V d2 = num % 10 height += (d1 < d2) - (d1 > d2) d1 = d2 num I/= 10 R height == 0
V num = 0 F nextNum()
L :num++ I riseEqFall(:num) L.break R :num
print(‘The first 200 numbers are:’) L 200
print(nextNum(), end' ‘ ’)
print()
L 0 .< 10'000'000 - 200 - 1
nextNum()
print(‘The 10,000,000th number is: ’nextNum())</lang>
- Output:
The first 200 numbers are: 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 The 10,000,000th number is: 41909002
8080 Assembly
<lang 8080asm>puts: equ 9 ; CP/M calls putch: equ 2 org 100h ;;; Print first 200 numbers lxi d,first mvi c,puts call 5 mvi b,200 ; 200 numbers f200: push b call next ; Get next number call pnum ; Print the number pop b ; Restore counter dcr b ; Are we there yet? jnz f200 ; If not, next number ;;; Find 10,000,000th number lxi d,tenmil mvi c,puts call 5 f1e7: call next ; Keep generating numbers until ten million reached jnz f1e7 ; Then print the number ;;; Print the current number pnum: lxi d,num pscan: dcx d ; Scan for zero ldax d ana a jnz pscan mvi c,puts ; Once found, print string jmp 5 ;;; Increment number until rises and falls are equal next: lxi h,num incdgt: mov a,m ; Get digit ana a ; If 0, then initialize jz grow inr a ; Otherwise, increment mov m,a ; Store back cpi '9'+1 ; Rollover? jnz idone ; If not, we're done mvi m,'0' ; If so, set digit to 0 dcx h ; And increment previous digit jmp incdgt grow: mvi m,'1' idone: lxi h,num ; Find rises and falls mvi b,0 ; B = rises - falls mov c,m ; C = right digit in comparison pair: dcx h mov a,m ; A = left digit in comparison ana a ; When zero, done jz check cmp c ; Compare left digit to right digit jc fall ; A<C = fall jnz rise ; A>C = rise nxdgt: mov c,a ; C is now left digit jmp pair ; Check next pair fall: dcr b ; Fall: decrement B jmp nxdgt rise: inr b ; Rise: increment B jmp nxdgt check: mov a,b ; If B=0 then rises and falls are equal ana a jnz next ; Otherwise, increment number and try again lxi h,ctr ; But if so, decrement the counter to 10 million mov a,m ; First byte sui 1 mov m,a inx h ; Second byte mov a,m sbb b ; B=0 here mov m,a inx h ; Third byte mov a,m sbb b mov m,a dcx h ; OR them together to see if the number is zero ora m dcx h ora m ret ;;; Strings first: db 'The first 200 numbers are:',13,10,'$' tenmil: db 13,10,10,'The 10,000,000th number is: $' ;;; Current number (stored as ASCII) db 0,0,0,0,0,0,0,0 num: db '0 $' ;;; 24-bit counter to keep track of ten million ctr: db 80h,96h,98h ; 1e7 = 989680h</lang>
- Output:
The first 200 numbers are: 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 The 10,000,000th number is: 41909002
8086 Assembly
<lang asm>puts: equ 9 ; MS-DOS print string cpu 8086 bits 16 org 100h section .text mov bp,98h ; BP:DI = 989680h = ten million mov di,9680h ;;; Print first 200 numbers mov dx,first ; Print message mov ah,puts int 21h n200: call next ; Get next number call pnum ; Print the number cmp di,95B8h ; Have we had 200 yet? ja n200 ; If not, print next number ;;; Print the 10 millionth number mov dx,tenmil ; Print message mov ah,puts int 21h n1e7: call next ; Get next number jnz n1e7 ; Until we have the 10 millionth ;;; Print the current number pnum: std ; Read backwards xchg si,di ; Keep DI safe mov di,num mov cx,9 xor al,al ; Find the first zero repnz scasb inc di ; Go to first digit inc di xchg si,di ; Put DI back mov dx,si ; Call DOS to print the number mov ah,puts int 21h ret ;;; Increment number until rises and falls are equal next: std ; Read number backwards .inc: mov bx,num .iloop: mov al,[bx] ; Get digit test al,al ; If uninitialized, write a 1 jz .grow inc ax ; Otherwise, increment mov [bx],al ; Write it back cmp al,'9'+1 ; Rollover? jnz .idone ; If not, the increment is done mov [bx],byte '0' ; But if so, this digit should be 0, dec bx ; and the next digit incremented. jmp .iloop .grow: mov [bx],byte '1' ; The number gains an extra digit .idone: xor bl,bl ; BL = rise and fall counter mov si,num lodsb ; Read first digit to compare to .pair: xchg ah,al ; Previous digit to compare lodsb ; Read next digit test al,al ; Done yet? jz .done cmp al,ah ; If not, compare the digits ja .fall ; If they are different, jb .rise ; there is a fall or a rise jmp .pair ; Otherwise, try next pair .fall: dec bl ; Fall: decrement BL jmp .pair .rise: inc bl ; Rise: increment BL jmp .pair .done: test bl,bl ; At the end, check if BL is zero jnz .inc ; If not, try next number sub di,1 ; Decrement the million counter in BP:DI sbb bp,0 mov ax,di ; Test if BP:DI is zero or ax,bp ret section .data ;;; Strings first: db 'The first 200 numbers are:',13,10,'$' tenmil: db 13,10,10,'The 10,000,000th number is: $' ;;; Current number, stored as ASCII db 0,0,0,0,0,0,0,0 num: db '0 $'</lang>
- Output:
The first 200 numbers are: 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 The 10,000,000th number is: 41909002
Ada
<lang Ada>with Ada.Text_Io; with Ada.Integer_Text_Io;
procedure Equal_Rise_Fall is
use Ada.Text_Io;
function Has_Equal_Rise_Fall (Value : Natural) return Boolean is Rises : Natural := 0; Falls : Natural := 0; Image : constant String := Natural'Image (Value); Last : Character := Image (Image'First + 1); begin for Pos in Image'First + 2 .. Image'Last loop if Image (Pos) > Last then Rises := Rises + 1; elsif Image (Pos) < Last then Falls := Falls + 1; end if; Last := Image (Pos); end loop; return Rises = Falls; end Has_Equal_Rise_Fall;
Value : Natural := 1; Count : Natural := 0;
begin
loop if Has_Equal_Rise_Fall (Value) then Count := Count + 1; if Count <= 200 then Ada.Integer_Text_Io.Put (Value, Width => 5); if Count mod 20 = 0 then New_Line; end if; end if; if Count = 10_000_000 then New_Line; Put_Line ("The 10_000_000th: " & Natural'Image (Value)); exit; end if; end if; Value := Value + 1; end loop;
end Equal_Rise_Fall;</lang>
- Output:
1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 The 10_000_000th: 41909002
ALGOL 68
... with a single counter for rises and falls.
<lang algol68>BEGIN
# returns TRUE if the number of digits in n followed by a higher digit (rises) # # equals the number of digits followed by a lower digit (falls) # # FALSE otherwise # PROC rises equals falls = ( INT n )BOOL: BEGIN INT rf := 0; INT prev := n MOD 10; INT v := n OVER 10; WHILE v > 0 DO INT d = v MOD 10; IF d < prev THEN rf +:= 1 # rise # ELIF d > prev THEN rf -:= 1 # fall # FI; prev := d; v OVERAB 10 OD; rf = 0 END; # rises equals falls # # task tests # print( ( "The first 200 numbers in the sequence are:", newline ) ); INT count := 0; INT max count = 10 000 000; FOR n WHILE count < max count DO IF rises equals falls( n ) THEN count +:= 1; IF count <= 200 THEN print( ( whole( n, -4 ) ) ); IF count MOD 20 = 0 THEN print( ( newline ) ) FI ELIF count = max count THEN print( ( newline, "The 10 millionth number in the sequence is ", whole( n, -8 ), ".", newline ) ) FI FI OD
END </lang>
- Output:
The first 200 numbers in the sequence are: 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 The 10 millionth number in the sequence is 41909002.
APL
<lang APL>risefall←{
⍝ Determine if a number is in the sequence inSeq←0=(+/2(<->)/10(⊥⍣¯1)⊢)
⍝ First 200 numbers ⎕←'The first 200 numbers are:' ⎕←(⊢(/⍨)inSeq¨)⍳404
⍝ 10,000,000th number ⍝ You can't just make a list that big and filter ⍝ it, because that will just get you a WS FULL. ⍝ Instead it's necessary to loop over them the old- ⍝ fashioned way ⍞←'The 10,000,000th number is: ' ⎕←1e7{⍺=0:⍵-1 ⋄ (⍺-inSeq ⍵)∇ ⍵+1}1
}</lang>
- Output:
The first 200 numbers are: 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 The 10,000,000th number is: 41909002
AWK
<lang AWK>
- syntax: GAWK -f NUMBERS_WITH_EQUAL_RISES_AND_FALLS.AWK
- converted from Go
BEGIN {
print("1-200:") while (1) { if (rises_equals_falls(++n)) { if (++count <= 200) { printf("%4d",n) if (count % 20 == 0) { printf("\n") } } if (count == 1E7) { printf("\n%d: %d",count,n) break } } } exit(0)
} function rises_equals_falls(n, d,falls,prev,rises) {
if (n < 10) { return(1) } prev = -1 while (n > 0) { d = n % 10 if (prev >= 0) { if (d < prev) { rises++ } else if (d > prev) { falls++ } } prev = d n = int(n / 10) } return(rises == falls)
} </lang>
- Output:
1-200: 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 10000000: 41909002
C
<lang C>#include <stdio.h>
/* Check whether a number has an equal amount of rises
* and falls */
int riseEqFall(int num) {
int rdigit = num % 10; int netHeight = 0; while (num /= 10) { netHeight += ((num % 10) > rdigit) - ((num % 10) < rdigit); rdigit = num % 10; } return netHeight == 0;
}
/* Get the next member of the sequence, in order,
* starting at 1 */
int nextNum() {
static int num = 0; do {num++;} while (!riseEqFall(num)); return num;
}
int main(void) {
int total, num; /* Generate first 200 numbers */ printf("The first 200 numbers are: \n"); for (total = 0; total < 200; total++) printf("%d ", nextNum()); /* Generate 10,000,000th number */ printf("\n\nThe 10,000,000th number is: "); for (; total < 10000000; total++) num = nextNum(); printf("%d\n", num); return 0;
}</lang>
- Output:
The first 200 numbers are: 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 The 10,000,000th number is: 41909002
C++
<lang cpp>#include <iomanip>
- include <iostream>
bool equal_rises_and_falls(int n) {
int total = 0; for (int previous_digit = -1; n > 0; n /= 10) { int digit = n % 10; if (previous_digit > digit) ++total; else if (previous_digit >= 0 && previous_digit < digit) --total; previous_digit = digit; } return total == 0;
}
int main() {
const int limit1 = 200; const int limit2 = 10000000; int n = 0; std::cout << "The first " << limit1 << " numbers in the sequence are:\n"; for (int count = 0; count < limit2; ) { if (equal_rises_and_falls(++n)) { ++count; if (count <= limit1) std::cout << std::setw(3) << n << (count % 20 == 0 ? '\n' : ' '); } } std::cout << "\nThe " << limit2 << "th number in the sequence is " << n << ".\n";
}</lang>
- Output:
The first 200 numbers in the sequence are: 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 The 10000000th number in the sequence is 41909002.
Cowgol
<lang cowgol>include "cowgol.coh";
- return the change in height of a number
sub height(n: uint32): (h: int8) is
h := 0; var dgt := (n % 10) as uint8; var prev: uint8; n := n / 10; while n > 0 loop prev := dgt; dgt := (n % 10) as uint8; n := n / 10; if prev < dgt then h := h + 1; elseif prev > dgt then h := h - 1; end if; end loop;
end sub;
var number: uint32 := 0; var seen: uint32 := 0; var col: uint8 := 10;
print("The first 200 numbers are:"); print_nl(); while seen < 10000000 loop
loop number := number + 1; if height(number) == 0 then break; end if; end loop; seen := seen + 1; if seen <= 200 then print_i32(number); col := col - 1; if col != 0 then print_char('\t'); else print_char('\n'); col := 10; end if; end if;
end loop;
print_nl(); print("The 10,000,000th number is: "); print_i32(number); print_nl();</lang>
- Output:
The first 200 numbers are: 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 The 10,000,000th number is: 41909002
F#
<lang fsharp> // A296712. Nigel Galloway: October 9th., 2020 let fN g=let rec fN Ψ n g=match n,Ψ with (0,0)->true |(0,_)->false |_->let i=n%10 in fN (Ψ + (compare i g)) (n/10) i in fN 0 g (g%10) let A296712=seq{1..2147483647}|>Seq.filter fN A296712|>Seq.take 200|>Seq.iter(printf "%d "); printfn"\n" [999999;9999999;99999999]|>List.iter(fun n->printfn "The %dth element is %d" (n+1) (Seq.item n A296712)) </lang>
- Output:
1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 The 1000000th element is 3284698 The 10000000th element is 41909002 The 100000000th element is 375551037
Factor
<lang factor>USING: grouping io kernel lists lists.lazy math math.extras prettyprint tools.memory.private ;
- rises-and-falls-equal? ( n -- ? )
0 swap 10 /mod swap [ 10 /mod rot over - sgn rotd + spin ] until-zero drop 0 = ;
- OEIS:A296712 ( -- list )
1 lfrom [ rises-and-falls-equal? ] lfilter ;
! Task "The first 200 numbers in OEIS:A296712 are:" print 200 OEIS:A296712 ltake list>array 20 group simple-table. nl
"The 10 millionth number in OEIS:A296712 is " write 9,999,999 OEIS:A296712 lnth commas print</lang>
- Output:
The first 200 numbers in OEIS:A296712 are: 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 The 10 millionth number in OEIS:A296712 is 41,909,002
Forth
<lang forth>: in-seq? ( n -- is N in the sequence? )
0 swap \ height 10 /mod \ digit and rest of number begin dup while \ as long as the number isn't zero... 10 /mod \ get next digit and quotient -rot swap \ retrieve previous digit over - sgn \ see if higher, lower or equal (-1, 0, 1) >r rot r> + \ add to height -rot swap \ quotient on top of stack repeat drop drop \ drop number and last digit 0= \ is height equal to zero?
- next-val ( n -- n: retrieve first element of sequence higher than N )
begin 1+ dup in-seq? until
- two-hundred
begin over 200 < while next-val dup . swap 1+ swap repeat
- ten-million
begin over 10000000 < while next-val swap 1+ swap repeat
0 0 \ top of stack: current index and number ." The first 200 numbers are: " two-hundred cr cr ." The 10,000,000th number is: " ten-million . cr bye</lang>
- Output:
The first 200 numbers are: 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 The 10,000,000th number is: 41909002
Fortran
<lang Fortran> PROGRAM A296712
INTEGER IDX, NUM, I
- Index and number start out at zero
IDX = 0 NUM = 0
- Find and write the first 200 numbers
WRITE (*,'(A)') 'The first 200 numbers are: ' DO 100 I = 1, 200 CALL NEXT NUM(IDX, NUM) WRITE (*,'(I4)',ADVANCE='NO') NUM IF (MOD(I,20).EQ.0) WRITE (*,*) 100 CONTINUE
- Find the 10,000,000th number
WRITE (*,*) WRITE (*,'(A)',ADVANCE='NO') 'The 10,000,000th number is: ' 200 CALL NEXT NUM(IDX, NUM) IF (IDX.NE.10000000) GOTO 200 WRITE (*,'(I8)') NUM STOP END
- Given index and current number, retrieve the next number
- in the sequence.
SUBROUTINE NEXT NUM(IDX, NUM) INTEGER IDX, NUM LOGICAL IN SEQ 100 NUM = NUM + 1 IF (.NOT. IN SEQ(NUM)) GOTO 100 IDX = IDX + 1 END
- See whether N is in the sequence
LOGICAL FUNCTION IN SEQ(N) INTEGER N, DL, DR, VAL, HEIGHT
- Get first digit and divide value by 10
DL = MOD(N, 10) VAL = N / 10 HEIGHT = 0 100 IF (VAL.NE.0) THEN
- Retrieve digits by modulo and division
DR = DL DL = MOD(VAL, 10) VAL = VAL / 10
- Record rise or fall
IF (DL.LT.DR) HEIGHT = HEIGHT + 1 IF (DL.GT.DR) HEIGHT = HEIGHT - 1 GOTO 100 END IF
- N is in the sequence if the final height is 0
IN SEQ = HEIGHT.EQ.0 RETURN END </lang>
- Output:
The first 200 numbers are: 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 The 10,000,000th number is: 41909002
FreeBASIC
<lang freebasic>function eqrf( n as uinteger ) as boolean
dim as string sn = str(n) dim as integer q = 0 for i as uinteger = 2 to len(sn) if asc(mid(sn,i,1)) > asc(mid(sn,i-1,1)) then q += 1 elseif asc(mid(sn,i,1)) < asc(mid(sn,i-1,1)) then q -= 1 end if next i if q = 0 then return true else return false
end function
dim as uinteger c = 0, i = 1 while c < 10000001
if eqrf(i) then c += 1 if c <= 200 then print i;" "; if c = 10000000 then print : print i end if i += 1
wend</lang>
- Output:
1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 41909002
Go
<lang go>package main
import "fmt"
func risesEqualsFalls(n int) bool {
if n < 10 { return true } rises := 0 falls := 0 prev := -1 for n > 0 { d := n % 10 if prev >= 0 { if d < prev { rises = rises + 1 } else if d > prev { falls = falls + 1 } } prev = d n /= 10 } return rises == falls
}
func main() {
fmt.Println("The first 200 numbers in the sequence are:") count := 0 n := 1 for { if risesEqualsFalls(n) { count++ if count <= 200 { fmt.Printf("%3d ", n) if count%20 == 0 { fmt.Println() } } if count == 1e7 { fmt.Println("\nThe 10 millionth number in the sequence is ", n) break } } n++ }
}</lang>
- Output:
The first 200 numbers in the sequence are: 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 The 10 millionth number in the sequence is 41909002
Haskell
<lang haskell>import Data.Char
pairs :: [a] -> [(a,a)] pairs (a:b:as) = (a,b):pairs (b:as) pairs _ = []
riseEqFall :: Int -> Bool riseEqFall n = rel (>) digitPairs == rel (<) digitPairs
where rel r = sum . map (fromEnum . uncurry r) digitPairs = pairs $ map digitToInt $ show n
a296712 :: [Int] a296712 = [n | n <- [1..], riseEqFall n]
main :: IO () main = do putStrLn "The first 200 numbers are: " putStrLn $ unwords $ map show $ take 200 a296712 putStrLn "" putStr "The 10,000,000th number is: " putStrLn $ show $ a296712 !! 9999999 </lang>
- Output:
The first 200 numbers are: 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 The 10,000,000th number is: 41909002
Java
<lang java>public class EqualRisesFalls {
public static void main(String[] args) { final int limit1 = 200; final int limit2 = 10000000; System.out.printf("The first %d numbers in the sequence are:\n", limit1); int n = 0; for (int count = 0; count < limit2; ) { if (equalRisesAndFalls(++n)) { ++count; if (count <= limit1) System.out.printf("%3d%c", n, count % 20 == 0 ? '\n' : ' '); } } System.out.printf("\nThe %dth number in the sequence is %d.\n", limit2, n); }
private static boolean equalRisesAndFalls(int n) { int total = 0; for (int previousDigit = -1; n > 0; n /= 10) { int digit = n % 10; if (previousDigit > digit) ++total; else if (previousDigit >= 0 && previousDigit < digit) --total; previousDigit = digit; } return total == 0; }
}</lang>
- Output:
The first 200 numbers in the sequence are: 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 The 10000000th number in the sequence is 41909002.
Julia
<lang julia>using Lazy
function rises_and_falls(n)
if n < 10 return 0, 0 end lastr, rises, falls = n % 10, 0, 0 while n != 0 n, r = divrem(n, 10) if r > lastr falls += 1 elseif r < lastr rises += 1 end lastr = r end return rises, falls
end
isA296712(x) = ((a, b) = rises_and_falls(x); return a == b)
function genA296712(N, M)
A296712 = filter(isA296712, Lazy.range(1)); j = 0 for i in take(200, A296712) j += 1 print(lpad(i, 4), j % 20 == 0 ? "\n" : "") end for i in take(M, A296712) j = i end println("\nThe $M-th number in sequence A296712 is $j.")
end
genA296712(200, 10_000_000)
</lang>
- Output:
1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 The 10000000-th number in sequence A296712 is 41909002.
MAD
<lang MAD> NORMAL MODE IS INTEGER
VECTOR VALUES FMT = $I8,1H:,I9*$ INTERNAL FUNCTION(NUM) ENTRY TO RISFAL. N=NUM DEPTH = 0 DIGA = N-(N/10)*10 N = N/10
LOOP WHENEVER N.E.0, FUNCTION RETURN DEPTH.E.0
DIGB = DIGA DIGA = N-(N/10)*10 N = N/10 WHENEVER DIGA.L.DIGB, DEPTH=DEPTH-1 WHENEVER DIGA.G.DIGB, DEPTH=DEPTH+1 TRANSFER TO LOOP END OF FUNCTION I=0 J=0
LOOP J=J+1
WHENEVER .NOT.RISFAL.(J), TRANSFER TO LOOP I=I+1 WHENEVER I.LE.200, PRINT FORMAT FMT, I, J WHENEVER I.L.10000000, TRANSFER TO LOOP PRINT FORMAT FMT, I, J END OF PROGRAM</lang>
- Output:
1: 1 2: 2 3: 3 4: 4 5: 5 6: 6 7: 7 8: 8 9: 9 10: 11 11: 22 12: 33 13: 44 14: 55 15: 66 16: 77 17: 88 18: 99 19: 101 20: 102 21: 103 22: 104 23: 105 24: 106 25: 107 26: 108 27: 109 28: 111 29: 120 30: 121 31: 130 32: 131 33: 132 34: 140 35: 141 36: 142 37: 143 38: 150 39: 151 40: 152 41: 153 42: 154 43: 160 44: 161 45: 162 46: 163 47: 164 48: 165 49: 170 50: 171 51: 172 52: 173 53: 174 54: 175 55: 176 56: 180 57: 181 58: 182 59: 183 60: 184 61: 185 62: 186 63: 187 64: 190 65: 191 66: 192 67: 193 68: 194 69: 195 70: 196 71: 197 72: 198 73: 201 74: 202 75: 203 76: 204 77: 205 78: 206 79: 207 80: 208 81: 209 82: 212 83: 213 84: 214 85: 215 86: 216 87: 217 88: 218 89: 219 90: 222 91: 230 92: 231 93: 232 94: 240 95: 241 96: 242 97: 243 98: 250 99: 251 100: 252 101: 253 102: 254 103: 260 104: 261 105: 262 106: 263 107: 264 108: 265 109: 270 110: 271 111: 272 112: 273 113: 274 114: 275 115: 276 116: 280 117: 281 118: 282 119: 283 120: 284 121: 285 122: 286 123: 287 124: 290 125: 291 126: 292 127: 293 128: 294 129: 295 130: 296 131: 297 132: 298 133: 301 134: 302 135: 303 136: 304 137: 305 138: 306 139: 307 140: 308 141: 309 142: 312 143: 313 144: 314 145: 315 146: 316 147: 317 148: 318 149: 319 150: 323 151: 324 152: 325 153: 326 154: 327 155: 328 156: 329 157: 333 158: 340 159: 341 160: 342 161: 343 162: 350 163: 351 164: 352 165: 353 166: 354 167: 360 168: 361 169: 362 170: 363 171: 364 172: 365 173: 370 174: 371 175: 372 176: 373 177: 374 178: 375 179: 376 180: 380 181: 381 182: 382 183: 383 184: 384 185: 385 186: 386 187: 387 188: 390 189: 391 190: 392 191: 393 192: 394 193: 395 194: 396 195: 397 196: 398 197: 401 198: 402 199: 403 200: 404 10000000: 41909002
Nim
<lang Nim>import strutils
func insequence(n: Positive): bool =
## Return true if "n" is in the sequence. if n < 10: return true var diff = 0 var prev = n mod 10 var n = n div 10 while n != 0: let digit = n mod 10 if digit < prev: inc diff elif digit > prev: dec diff prev = digit n = n div 10 result = diff == 0
iterator a297712(): (int, int) =
## Yield the positions and the numbers of the sequence. var n = 1 var pos = 0 while true: if n.insequence: inc pos yield (pos, n) inc n
echo "First 200 numbers in the sequence:" for (pos, n) in a297712():
if pos <= 200: stdout.write ($n).align(3), if pos mod 20 == 0: '\n' else: ' ' elif pos == 10_000_000: echo "\nTen millionth number in the sequence: ", n break</lang>
- Output:
First 200 numbers in the sequence: 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 Ten millionth number in the sequence: 41909002
Perl
<lang perl>#!/usr/bin/perl
use strict; use warnings;
sub rf
{ local $_ = shift; my $sum = 0; $sum += $1 <=> $2 while /(.)(?=(.))/g; $sum }
my $count = 0; my $n = 0; my @numbers; while( $count < 200 )
{ rf(++$n) or $count++, push @numbers, $n; }
print "first 200: @numbers\n" =~ s/.{1,70}\K\s/\n/gr;
$count = 0; $n = 0; while( $count < 10e6 )
{ rf(++$n) or $count++; }
print "\n10,000,000th number: $n\n";</lang>
- Output:
first 200: 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 10,000,000th number: 41909002
Phix
<lang Phix>atom t1 = time()+1 integer count = 0, n = 0 printf(1,"The first 200 numbers are:\n") while true do
n += 1 integer rmf = 0, l = remainder(n,10), r = floor(n/10) while r do integer p = remainder(r,10) rmf += compare(l,p) l = p r = floor(r/10) end while if rmf=0 then count += 1 if count<=200 then printf(1,"%3d ",n) if remainder(count,20)=0 then printf(1,"\n") end if end if if count == 1e7 then progress("") printf(1,"\nThe %,dth number is %,d\n",{count,n}) exit end if if time()>t1 then progress("%,d:%,d\r",{count,n}) t1 = time()+1 end if end if
end while</lang>
- Output:
The first 200 numbers are: 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 The 10,000,000th number is 41,909,002
Python
<lang python>import itertools
def riseEqFall(num):
"""Check whether a number belongs to sequence A296712.""" height = 0 d1 = num % 10 num //= 10 while num: d2 = num % 10 height += (d1<d2) - (d1>d2) d1 = d2 num //= 10 return height == 0
def sequence(start, fn):
"""Generate a sequence defined by a function""" num=start-1 while True: num += 1 while not fn(num): num += 1 yield num
a296712 = sequence(1, riseEqFall)
- Generate the first 200 numbers
print("The first 200 numbers are:") print(*itertools.islice(a296712, 200))
- Generate the 10,000,000th number
print("The 10,000,000th number is:") print(*itertools.islice(a296712, 10000000-200-1, 10000000-200))
- It is necessary to subtract 200 from the index, because 200 numbers
- have already been consumed.
</lang>
- Output:
The first 200 numbers are: 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 The 10,000,000th number is: 41909002
Raku
<lang perl6>use Lingua::EN::Numbers; use Base::Any;
sub rf (int $base = 10, $batch = Any, &op = &infix:<==>) {
my %batch = batch => $batch if $batch; flat (1 .. ∞).hyper(|%batch).map: { my int ($this, $last) = $_, $_ % $base; my int ($rise, $fall) = 0, 0; while $this { my int $rem = $this % $base; $this = $this div $base; if $rem > $last { $fall = $fall + 1 } elsif $rem < $last { $rise = $rise + 1 } $last = $rem } next unless &op($rise, $fall); $_ }
}
- The task
my $upto = 200; put "Rise = Fall:\nFirst {$upto.&cardinal} (base 10):"; .put for rf[^$upto]».fmt("%3d").batch(20);
$upto = 10_000_000; put "\nThe {$upto.&ordinal} (base 10): ", comma rf(10, 65536)[$upto - 1];
- Other bases and comparisons
put "\n\nGeneralized for other bases and other comparisons:"; $upto = ^5; my $which = "{tc $upto.map({.exp(10).&ordinal}).join: ', '}, values in some other bases:";
put "\nRise = Fall: $which"; for <3 296691 4 296694 5 296697 6 296700 7 296703 8 296706 9 296709 10 296712
11 296744 12 296747 13 296750 14 296753 15 296756 16 296759 20 296762 60 296765> -> $base, $oeis { put "Base {$base.fmt(<%2d>)} (https://oeis.org/A$oeis): ", $upto.map({rf(+$base, Any)[.exp(10) - 1].&to-base($base)}).join: ', '
}
put "\nRise > Fall: $which"; for <3 296692 4 296695 5 296698 6 296701 7 296704 8 296707 9 296710 10 296713
11 296745 12 296748 13 296751 14 296754 15 296757 16 296760 20 296763 60 296766> -> $base, $oeis { put "Base {$base.fmt(<%2d>)} (https://oeis.org/A$oeis): ", $upto.map({rf(+$base, Any, &infix:«>»)[.exp(10) - 1].&to-base($base)}).join: ', ' }
put "\nRise < Fall: $which"; for <3 296693 4 296696 5 296699 6 296702 7 296705 8 296708 9 296711 10 296714
11 296746 12 296749 13 296752 14 296755 15 296758 16 296761 20 296764 60 296767> -> $base, $oeis { put "Base {$base.fmt(<%2d>)} (https://oeis.org/A$oeis): ", $upto.map({rf(+$base, Any, &infix:«<»)[.exp(10) - 1].&to-base($base)}).join: ', ' }</lang>
- Output:
Rise = Fall: First two hundred (base 10): 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 The ten millionth (base 10): 41,909,002 Generalized for other bases and other comparisons: Rise = Fall: First, tenth, one hundredth, one thousandth, ten thousandth, values in some other bases: Base 3 (https://oeis.org/A296691): 1, 201, 22112, 10101111, 1100022001 Base 4 (https://oeis.org/A296694): 1, 111, 3333, 221012, 13002120 Base 5 (https://oeis.org/A296697): 1, 102, 1441, 40011, 1431201 Base 6 (https://oeis.org/A296700): 1, 55, 512, 20424, 400402 Base 7 (https://oeis.org/A296703): 1, 44, 365, 12620, 155554 Base 8 (https://oeis.org/A296706): 1, 33, 316, 7466, 60404 Base 9 (https://oeis.org/A296709): 1, 22, 275, 5113, 40217 Base 10 (https://oeis.org/A296712): 1, 11, 252, 3396, 29201 Base 11 (https://oeis.org/A296744): 1, A, 216, 2240, 21718 Base 12 (https://oeis.org/A296747): 1, A, 201, 10AA, 19723 Base 13 (https://oeis.org/A296750): 1, A, 1B8, A0A, 172A7 Base 14 (https://oeis.org/A296753): 1, A, 1B5, 8B9, 14B81 Base 15 (https://oeis.org/A296756): 1, A, 1B2, 7D4, 11BBA Base 16 (https://oeis.org/A296759): 1, A, 1A9, 716, 10424 Base 20 (https://oeis.org/A296762): 1, A, 196, 523, 8011 Base 60 (https://oeis.org/A296765): 1, A, ff, 1f2, 63Q Rise > Fall: First, tenth, one hundredth, one thousandth, ten thousandth, values in some other bases: Base 3 (https://oeis.org/A296692): 12, 1222, 122202, 12222001, 2001200001 Base 4 (https://oeis.org/A296695): 12, 233, 12113, 1003012, 13131333 Base 5 (https://oeis.org/A296698): 12, 122, 2302, 112013, 1342223 Base 6 (https://oeis.org/A296701): 12, 45, 1305, 20233, 333134 Base 7 (https://oeis.org/A296704): 12, 34, 1166, 11612, 140045 Base 8 (https://oeis.org/A296707): 12, 26, 1013, 4557, 106756 Base 9 (https://oeis.org/A296710): 12, 25, 348, 2808, 36781 Base 10 (https://oeis.org/A296713): 12, 24, 249, 2345, 23678 Base 11 (https://oeis.org/A296745): 12, 23, 223, 1836, 15806 Base 12 (https://oeis.org/A296748): 12, 1B, 166, 1623, 12534 Base 13 (https://oeis.org/A296751): 12, 1B, 145, 149B, A069 Base 14 (https://oeis.org/A296754): 12, 1B, 12B, 1393, 6BC9 Base 15 (https://oeis.org/A296757): 12, 1B, 11A, 12B7, 568E Base 16 (https://oeis.org/A296760): 12, 1B, CD, 1206, 466A Base 20 (https://oeis.org/A296763): 12, 1B, 7E, 6BF, 2857 Base 60 (https://oeis.org/A296766): 12, 1B, 2i, Lp, 66U Rise < Fall: First, tenth, one hundredth, one thousandth, ten thousandth, values in some other bases: Base 3 (https://oeis.org/A296693): 10, 221, 22220, 10021001, 1012110000 Base 4 (https://oeis.org/A296696): 10, 210, 3330, 231210, 13132000 Base 5 (https://oeis.org/A296699): 10, 43, 2420, 43033, 2030042 Base 6 (https://oeis.org/A296702): 10, 43, 1540, 25543, 403531 Base 7 (https://oeis.org/A296705): 10, 43, 1010, 10051, 206260 Base 8 (https://oeis.org/A296708): 10, 43, 660, 5732, 75051 Base 9 (https://oeis.org/A296711): 10, 43, 643, 5010, 60873 Base 10 (https://oeis.org/A296714): 10, 43, 621, 4120, 44100 Base 11 (https://oeis.org/A296746): 10, 43, 544, 3243, 31160 Base 12 (https://oeis.org/A296749): 10, 43, 520, 2A71, 18321 Base 13 (https://oeis.org/A296752): 10, 43, 422, 2164, B624 Base 14 (https://oeis.org/A296755): 10, 43, 310, 1CA3, A506 Base 15 (https://oeis.org/A296758): 10, 43, E8, 1A20, 9518 Base 16 (https://oeis.org/A296761): 10, 43, E8, 10D0, 860D Base 20 (https://oeis.org/A296764): 10, 43, E8, G33, 5F43 Base 60 (https://oeis.org/A296767): 10, 43, E8, j9, ZUT
REXX
To do the heavy lifting, this REXX program constructs a table of every two-digit sequence which indicates a
rise (+1), fall (-1), or neither (0).
<lang rexx>/*REXX pgm finds and displays N numbers that have an equal number of rises and falls,*/
parse arg n . /*obtain optional argument from the CL.*/
if n== | n=="," then n= 200 /*Not specified? Then use the default.*/
append= n>0 /*a flag that is used to append numbers*/
n= abs(n) /*use the absolute value of N. */
call init /*initialize the rise/fall database. */
do j=1 until #==n /*test integers until we have N of them*/ s= 0 /*initialize the sum of rises/falls. */ do k=1 for length(j)-1 /*obtain a set of two digs from number.*/ t= substr(j, k, 2) /*obtain a set of two digs from number.*/ s= s + @.t /*sum the rises and falls in the number*/ end /*k*/ if s\==0 then iterate /*Equal # of rises & falls? Then add it*/ #= # + 1 /*bump the count of numbers found. */ if append then $= $ j /*append to the list of numbers found. */ end /*j*/
if append then call show /*display a list of N numbers──►term.*/
else say 'the ' commas(n)th(n) " number is: " commas(j) /*show Nth #.*/
exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg _; do c=length(_)-3 to 1 by -3; _=insert(',', _, c); end; return _ th: parse arg th; return word('th st nd rd',1+(th//10)*(th//100%10\==1)*(th//10<4)) /*──────────────────────────────────────────────────────────────────────────────────────*/ init: @.= 0; do i=1 for 9; _= i' '; @._= 1; _= '0'i; @._= +1; end /*i*/
do i=10 to 99; parse var i a 2 b; if a>b then @.i= -1 else if a<b then @.i= +1 end /*i*/; #= 0; $=; return
/*──────────────────────────────────────────────────────────────────────────────────────*/ show: say 'the first ' commas(#) " numbers are:"; say; w= length( word($, #) )
_=; do o=1 for n; _= _ right( word($, o), w); if o//20\==0 then iterate say substr(_, 2); _= /*display a line; nullify a new line. */ end /*o*/ /* [↑] display 20 numbers to a line.*/
if _\== then say substr(_, 2); return /*handle any residual numbers in list. */</lang>
- output when using the default input:
the first 200 numbers are: 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404
- output when using the input of: -10000000
the 10,000,000th number is: 41,909,002
Sidef
<lang ruby>func isok(arr) {
var diffs = arr.map_cons(2, {|a,b| a - b }) diffs.count { .is_pos } == diffs.count { .is_neg }
}
var base = 10
with (200) {|n|
say "First #{n} terms (base #{base}):" n.by { isok(.digits(base)) && .is_pos }.each_slice(20, {|*a| say a.map { '%3s' % _ }.join(' ') })
}
with (1e7) {|n| # takes a very long time
say "\nThe #{n.commify}-th term (base #{base}): #{ n.th { isok(.digits(base)) && .is_pos }.commify}"
}</lang>
- Output:
First 200 terms (base 10): 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 The 10,000,000-th term (base 10): 41,909,002
Swift
<lang swift>import Foundation
func equalRisesAndFalls(_ n: Int) -> Bool {
var total = 0 var previousDigit = -1 var m = n while m > 0 { let digit = m % 10 m /= 10 if previousDigit > digit { total += 1 } else if previousDigit >= 0 && previousDigit < digit { total -= 1 } previousDigit = digit } return total == 0
}
var count = 0 var n = 0 let limit1 = 200 let limit2 = 10000000 print("The first \(limit1) numbers in the sequence are:") while count < limit2 {
n += 1 if equalRisesAndFalls(n) { count += 1 if count <= limit1 { print(String(format: "%3d", n), terminator: count % 20 == 0 ? "\n" : " ") } }
} print("\nThe \(limit2)th number in the sequence is \(n).")</lang>
- Output:
The first 200 numbers in the sequence are: 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 The 10000000th number in the sequence is 41909002.
Wren
<lang ecmascript>import "/fmt" for Fmt
var risesEqualsFalls = Fn.new { |n|
if (n < 10) return true var rises = 0 var falls = 0 var prev = -1 while (n > 0) { var d = n%10 if (prev >= 0) { if (d < prev) { rises = rises + 1 } else if (d > prev) { falls = falls + 1 } } prev = d n = (n/10).floor } return rises == falls
}
System.print("The first 200 numbers in the sequence are:") var count = 0 var n = 1 while (true) {
if (risesEqualsFalls.call(n)) { count = count + 1 if (count <= 200) { Fmt.write("$3d ", n) if (count % 20 == 0) System.print() } if (count == 1e7) { Fmt.print("\nThe 10 millionth number in the sequence is $,d.", n) break } } n = n + 1
}</lang>
- Output:
The first 200 numbers in the sequence are: 1 2 3 4 5 6 7 8 9 11 22 33 44 55 66 77 88 99 101 102 103 104 105 106 107 108 109 111 120 121 130 131 132 140 141 142 143 150 151 152 153 154 160 161 162 163 164 165 170 171 172 173 174 175 176 180 181 182 183 184 185 186 187 190 191 192 193 194 195 196 197 198 201 202 203 204 205 206 207 208 209 212 213 214 215 216 217 218 219 222 230 231 232 240 241 242 243 250 251 252 253 254 260 261 262 263 264 265 270 271 272 273 274 275 276 280 281 282 283 284 285 286 287 290 291 292 293 294 295 296 297 298 301 302 303 304 305 306 307 308 309 312 313 314 315 316 317 318 319 323 324 325 326 327 328 329 333 340 341 342 343 350 351 352 353 354 360 361 362 363 364 365 370 371 372 373 374 375 376 380 381 382 383 384 385 386 387 390 391 392 393 394 395 396 397 398 401 402 403 404 The 10 millionth number in the sequence is 41,909,002.